A Subarray Problem

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

You are given a permutation \(a\) of the integers from \(1\) to \(N\). You want to find

\[ \displaystyle \sum_{l=1}^{N}{\sum_{r=l}^{N}{\min(a_l,a_{l+1},\ldots,a_r)}} \]

In other words, let \(M_{l,r} = \min(a_l,a_{l+1},\ldots,a_r)\). You want to find the sum of \(M_{l,r}\) for all \(1 \le l \le r \le N\).

Input Specification

The first line will contain the integer \(N\ (1 \le N \le 2 \times 10^5)\).

The next line will contain \(N\) space-separated integers, \(a_i\ (1 \le a_i \le N)\). \(a\) is guaranteed to be pairwise distinct. In other words, \(a_i\) forms a permutation.

Output Specification

The answer to the problem. Note that the answer may not fit in a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85

Comments

There are no comments at the moment.