19833번 - Equal Maximums 다국어

Sasha is preparing for programming contests, so he is studying data structures and corresponding problems. One common problem he has noticed is 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 "find the maximum value in a range from the $i$-th element to the $j$-th one", so the problem is to calculate $\max \{a_i, a_{i+1}, \ldots, a_j\}$.

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

Now Sasha is wondering, how many ways are there 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$.

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: array elements (they are positive and don't exceed $10^9$).

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

Pairs of ranges from the first sample: