Equal Maximums

Time limit1sMemory limit512 MB

Summary

Count quadruples of indices i<=j<k<=l where the maximum of a[i..j] equals the maximum of a[k..l], modulo 1e9+7, for n up to 100000.

Level: Hard8 of 10
Topics: Array, Stack, Combinatorics, Implementation
Solved: No attempts yet

Problem

Sasha is preparing for programming contests, so he is studying data structures and related problems. One common problem he has noticed is the Range Maximum Query.

That problem is defined as follows. There is an array $a$ of $n$ integers: $a_1, a_2, \ldots, a_n$ . One has to answer queries of the form "find the maximum value in the range from the $i$ -th element to the $j$ -th one", so the value to compute is $\max \{a_i, a_{i+1}, \ldots, a_j\}$ .

Of course, this task is not difficult for Sasha, and soon he had a very fast program that answers such queries. Looking at the answers, he noticed that the answers for different queries are often the same.

Now Sasha wonders how many ways there are to choose a pair of non-overlapping ranges that have equal maximum elements.

Your task is to help Sasha. Find the number of quadruples $i$ , $j$ , $k$ , $l$ such that $1 \le i \le j < k \le l \le n$ and $\max\{a_i, a_{i+1}, \ldots, a_j\} = \max\{a_k, a_{k+1}, \ldots, a_l\}$ . Since that number can be quite large, you have to output it modulo $1\,000\,000\,007$ .

Input

The first line of input contains one integer $n$ , the length of Sasha's array ( $2 \le n \le 100\,000$ ). The second line of input contains $n$ integers, the array elements. They are positive and do not exceed $10^9$ .

Output

Output the number of pairs of non-overlapping ranges with equal maximums, modulo $10^9 + 7$ .

Hint

Pairs of ranges from the first sample:


$[\mathbf{3}], [\mathbf{3}], 4, 4, 3, 2$	$i=1$	$j=1$	$k=2$	$l=2$
$[\mathbf{3}], 3, 4, 4, [\mathbf{3}], 2$	$i=1$	$j=1$	$k=5$	$l=5$
$[\mathbf{3}], 3, 4, 4, [\mathbf{3}, 2]$	$i=1$	$j=1$	$k=5$	$l=6$
$[\mathbf{3}, \mathbf{3}], 4, 4, [\mathbf{3}], 2$	$i=1$	$j=2$	$k=5$	$l=5$
$[\mathbf{3}, \mathbf{3}], 4, 4, [\mathbf{3}, 2]$	$i=1$	$j=2$	$k=5$	$l=6$
$3, [\mathbf{3}], 4, 4, [\mathbf{3}], 2$	$i=2$	$j=2$	$k=5$	$l=5$
$3, [\mathbf{3}], 4, 4, [\mathbf{3}, 2]$	$i=2$	$j=2$	$k=5$	$l=6$
$[3, 3, \mathbf{4}], [\mathbf{4}], 3, 2$	$i=1$	$j=3$	$k=4$	$l=4$
$[3, 3, \mathbf{4}], [\mathbf{4}, 3], 2$	$i=1$	$j=3$	$k=4$	$l=5$
$[3, 3, \mathbf{4}], [\mathbf{4}, 3, 2]$	$i=1$	$j=3$	$k=4$	$l=6$
$3, [3, \mathbf{4}], [\mathbf{4}], 3, 2$	$i=2$	$j=3$	$k=4$	$l=4$
$3, [3, \mathbf{4}], [\mathbf{4}, 3], 2$	$i=2$	$j=3$	$k=4$	$l=5$
$3, [3, \mathbf{4}], [\mathbf{4}, 3, 2]$	$i=2$	$j=3$	$k=4$	$l=6$
$3, 3, [\mathbf{4}], [\mathbf{4}], 3, 2$	$i=3$	$j=3$	$k=4$	$l=4$
$3, 3, [\mathbf{4}], [\mathbf{4}, 3], 2$	$i=3$	$j=3$	$k=4$	$l=5$
$3, 3, [\mathbf{4}], [\mathbf{4}, 3, 2]$	$i=3$	$j=3$	$k=4$	$l=6$

Examples2

Example 1
Input
```
6
3 3 4 4 3 2
```
Expected output
```
16
```
Example 2
Input
```
12
1 3 2 3 4 1 3 4 3 2 2 5
```
Expected output
```
177
```