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 ≤ 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 mandatorys 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-saparated integers A₁, A₂, ..., A_n (0 ≤ A_i ≤ 10⁹) - 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 10⁹ + 7 (1000000007).

Example

Input:
5
5 3 0 9 8 
Output:
21