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 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 (1 ≤ n ≤ 500000).
The second line contains n space-separated integers A1, A2 ... An (0 ≤ Ai ≤ 109) - 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 |