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  \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.