## A Subarray Problem

View as PDF

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