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 \(10^9\). 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 \leq N \leq 10^5)\)
Second line: \(N\) denoting all the randomly-generated integers of an array \(A\) \((1 \leq A_i \leq 10^9)\)

Output format

Print an integer denoting the maximum sum of all the subarrays of the array \(A\).

Test data

In 30% of tests: \((1 \leq N \leq 10^3)\)
In 70% of tests: \((1 \leq N \leq 10^5)\)

Second sample input
15
588365128 594308557 450352119 92346171 931643688 46573784 706263519 857528857 594978510 433723137 726627302 113654230 428591921 937716247 772920030

Second sample output
45