A bitonic subsequence is a sequence which is first non-decreasing and then non-increasing.
You are given an array of size N. You need to find the number of bitonic subsequences.
As the number can be very large, output it modulo 1e9 + 7.
Input
First line contains a single integer N, the size of array
The next line contains N integers, the elements of the array.
Output
Output number of bitonic subsequences modulo 1e9 + 7.
Constraints
1 ≤ N ≤ 100000, size of array
1 ≤ A[i] ≤ 109
Limits
Time: 2 second
Memory: 256 MB