Description

 

Given an sequence a₁, a₂, ..., a_N.

Let Max（i, j） be the maximum among a_i, a_i+1, ..., a_j.

Please find the answer to Σ_{i = 1, 2, ...,N} Σ_{j = i, i+1, ..., N} M（i, j）.

 

For example, if the sequence is 1, 2, 3.

Then M(1, 1) = 1, M(1, 2) = 2, M(1, 3) = 3, M(2, 2) = 2, M(2, 3) = 3, M(3, 3) = 3

Σ_{i = 1, 2, 3} Σ_{j = i, i+1, ..., 3} M（i, j）= M(1, 1) + M(1, 2) + M(1, 3) + M(2, 2) + M(2, 3) + M(3, 3) = 14.

 

To prevent TLE, add the following code at the first line of your main function and don't use endl in your code.

ios::sync_with_stdio(0); cin.tie(0);

 

 

Input

 

The first line of the input contains an integer N, the length of the sequence.

The second line contains N numbers a₁, a₂, ..., a_N.

Testcase:

• For testcase 1 and 2, N <= 300.
• For testcase 3 and 4, N <= 5000.
• For testcase 5 and 6, N <= 100000.
• For testcase 7 and 8, N <= 2000000.

 

Remember to use long long to store the answer.

If you solve this problem by brute force, you can pass the the testcases 1 to 4.

 

Output

 

Please output a number as the answer.

Remember to add new line in the end.

 

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss