You are given an integer array A of length N. In all the tests, each element of the array A is a random value in between 1 to 109. The cost of the array is equal to the product of its length and the number of maximum changes. The number of maximum changes can be determined as follows:
Assume that cur is equal to 0 and mx is equal to the first element of the array, iterate over the array, and each time if the current element is greater than mx, then increment cur. The number of maximum changes in the array will be cur.
Your task is to divide an array A into contiguous subarrays to maximize the sum of costs of all the subarrays (each element of the array A must be exactly in one subarray).
Input format
- First line: An integer N (1≤N≤105)
- Second line: N denoting all the randomly-generated integers of an array A (1≤Ai≤109)
Output format
Print an integer denoting the maximum sum of all the subarrays of the array A.
Test data
In 30% of tests: (1≤N≤103)
In 70% of tests: (1≤N≤105)
Second sample input
15
588365128 594308557 450352119 92346171 931643688 46573784 706263519 857528857 594978510 433723137 726627302 113654230 428591921 937716247 772920030
Second sample output
45
In first sample test case, you can divide an array A onto two subarrays: [1,2] and [3,10].
First subarray is [460626451, 802090732] − the number of maximum changes is 1 (460626451, 802090732) (note that the initial value does not count as first maximum change) and the length of subarray is 2. So, the cost is equal to 2.
Second subarray is [277246428, 661369649, 388684428, 784303821, 376287098, 656422756, 9301599, 25720377] − the number of maximum changes is 2 (277246428, 661369649, 784303821) and the length of subarray is 8. So, the cost is equal to 16.
The answer is sum of costs − 18.
