SP27218 HJB - Segmentation

Bobs just got an array $A$ of $n$ integers from his mother Ksenxi. She asked him to calculate the goodness of $A$. Let's define $f(a, b)$ of $A$ as minimum value on interval $[a, b]$ in $A$. Goodness of $A$ is the number of pairs of segments $[a, b]$, $[c, d]$ such that $1 \leq a \leq b < c \leq d \leq n$ and $f(a, b) \leq f(c, d)$. Since Bobs is writing an essay on matura in a few days he is now reading short summaries of books on the mandatory reading list so he needs your help to answer this hard question to his mom.

The first line of the input contains an integer $n$ ($1 \leq n \leq 500000$). The second line contains n space-separated integers $A_1, A_2,\ldots,A_n$ ($0 \leq A_i \leq 10^9$) - the array elements.

Print out a single integer - the goodness of A. As the answer can be quite a large number, you should print it modulo **10 $ ^{9} $ + 7** (**1000000007**).