HJB - Segmentation

no tags 

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 that1 ≤ a ≤ b < c ≤ d ≤ n and f(a, b) ≤ 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.

Input

The first line of the input contains an integer n (1n500000).
The second line contains n space-separated integers A1, A2 ... An (0 ≤ Ai109) - the array elements.

Output

Print out a single integer - the goodness of A. As the answer can be quite a large number, you should print it modulo 109 + 7 (1000000007).

Example

Input:
5
5 3 0 9 8 

Output:
21

hide comments
Ivan Paljak: 2019-08-19 15:30:58

True animal problem

Josip Klepec: 2016-07-01 14:32:30

Good for thinking :)

linkret: 2016-06-28 00:15:56

Not easy

Vedran Kurdija: 2016-06-15 09:42:15

Excellent problem.

Adrian Beker: 2016-06-13 21:25:07

Very nice problem :D


Added by:Stjepan Pozgaj
Date:2016-06-10
Time limit:2s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:own problem