Fenwick tree

ID 38509. Substrings of subsequences

Let's call a subsequence of array a a non-empty array b such that it can be obtained from array a by deleting some (possibly none) elements of array a. For example, array [1,3]  is a sequence of array [1,2,3] , but [3,1]  is not.

Let's call a subsegment of array a a non-empty array b such that it can be obtained by deleting several (possibly none) of the first and last elements of array a. For example, [1,2]  is a subsegment of the array [1,2,3] , but [1,3]  is not. It is easy to see that an array of length n has exactly  \( {n(n+1) \over 2}\)  subsegments.

Let's call an array a of length n increasing if for any 1 ≤ i≤ n a_i ≤ a_i+1.

The monotonicity of an array is the number of its increasing subsegments.

Given an array a of length n. Calculate the sum of monotonicities over all its subsequences. Since the answer can be very large, print it modulo 10⁹+7.

Input
The first line contains an integer n (1 ≤ n ≤ 200000) — array length a.
The second line contains n integers (1 ≤ a_i ≤ 200000) — array elements a.

Imprint
Print a single integer — the sum of the monotonicities of all subsequences modulo 10⁹+7.

Note
In the first test case, the array has 7 subsequences:

• Array [1]  has exactly one subsegment and is ascending.
• The array [2]   has exactly one subsegment and is increasing.
• The array [3]  has exactly one subsegment and is increasing.
• The array [1,2]  has three subsegments ([1], [2], [1,2] ) and they are all increasing.
• The array [1,3]  has three subsegments ([1], [3], [1,3] ) and they are all increasing.
• The array [3,2]   has three subsegments ([3], [2], [3, 2] ), but only two of them ([3]  and [2] ) are ascending.
• The array [1,3,2]  has six subsegments ([1], [3], [2], [1,3], [3,2], [1,3,2] ) and four of them ([1], [3], [2], [1,3] ) are increasing.

Examples