Time limit: 1 second Memory limit: 256 megabytes ---------- After a long day, Amin has decided to escape the Pardis Code land and take a rest. But Romina has noticed and wants to prevent his escape. However, Amin suggests solving a problem in exchange for being allowed to leave. Initially, a permutation is written on the board. In each step, Romina writes a new sequence on the board and erases the previous one. The new sequence is written by considering every two consecutive numbers: + If the number of elements in the current sequence on the board is odd, she selects the larger number and writes it below them in the new sequence. + If the number of elements in the current sequence on the board is even, she selects the smaller number and writes it below them in the new sequence. Similarly, after Romina's operations, in each step, a new sequence with one fewer element is written on the board, and then the previous sequence is erased. These steps are repeated until only one number remains on the board. Now, Romina wonders: if she starts the game for all different sequences obtained by erasing a portion from the right side and a portion from the left side of the initial sequence (i.e., all contiguous subarrays) and writes the remaining final number in her notebook, what is the sum of all numbers written in her notebook? Help Amin solve the problem so he can rest. Since the total sum might be large, output its remainder modulo $10^9 + 7$. # Input The first line contains an integer $N$, representing the number of elements in the initial permutation. $$ 1 \leq N \leq 2 \times 10^5 $$ The next line contains $N$ integers, which are the elements of the permutation from left to right. $$ 1 \le a_i \le n $$ It is guaranteed that the initial sequence is a permutation and contains no duplicate numbers. # Output Output the remainder of the sum of all answers for all contiguous subarrays of the initial permutation modulo $10^9 + 7$. # Example ## Sample Input 1 ``` 5 1 2 3 4 5 ``` ## Sample Output 1 ``` 42 ``` ## Sample Input 2 ``` 4 1 3 2 4 ``` ## Sample Output 2 ``` 23 ```