Element Swapping

Problem Statement

Element Swapping Problem Description You are given an array arr of n integers, indexed from 0 to n - 1 . You may repeat the following operation any number of times (possibly zero): Choose an index i with 0 <= i < n - 1 and swap the elements currently at positions i and i + 1 . Every element of the array may take part in at most one swap during the whole process. The strength of index i is arr[i] * (i + 1) , using 0-based indexing, and the total strength of the array is the sum of the strengths of all of its indices. Report the maximum total strength that the array can have after the operations have been applied optimally. Input Format The first line contains a single integer n , the number of elements in the array. Each of the next n lines contains a single integer; the integer on line 1 + i is arr[i] . Output Format Print a single integer on its own line: the maximum total strength achievable. Constraints 1 <= n <= 15000 1 <= arr[i] <= 10^9 for every 0 <= i < n