Maruo and the Sequence

sazerterus25 BUET CSE Fest 2019 Inter...
Limits 2s, 512 MB

Maruo has a sequece A = {a1,a2,......an}.
Let us define a function func(A,l,r) which is the minimum i such that ai is the maximum value where l<=i<=r.
Two sequences A and B are similar if they have the same length n and for every 1<=l<=r<=n , func(A,l,r) = func(B,l,r).
For any given sequence A={a1,a2,......an}, we define the weight of a sequence B={b1,b2,......bn} be
∑bi, where 1<=i<=n, if the two sequences A and B are similar. Otherwise, we let the weight be equal to 0. If each element of B is chosen independently and uniform randomly between 0 and 1, find the expected weight of B.

Please note that the elements of B are real numbers between 0 and 1 inclusive, and not necessarily only 0 or 1.

Input

The first line will contain n (the length of the sequence) 1<=n<=1000000.
The second line contains n integers (1<=ai<=n) denoting the sequence.

Output

The expected weight will be a rational number p/q, where p and q are co-prime numbers.
Output the answer modulo 109+7 i.e. output pq-1 modulo 109+7.

Sample

InputOutput
3
1 2 3
250000002

Submit

Login to submit.

Statistics

100% Solution Ratio
intrabuet19Earliest, Aug '19
NirjhorFastest, 0.1s
intrabuet19Lightest, 21 MB
NirjhorShortest, 989B
Toph uses cookies. By continuing you agree to our Cookie Policy.