The Maximum After Erasing

Time limit1sMemory limit512 MB

Summary

Given a permutation, sum the maximum of the remaining elements over every way to delete two disjoint intervals, modulo 10^9+7.

Level: Medium7 of 10
Topics: Array, Stack, Prefix sum
Solved: No attempts yet

Problem

A permutation $A$ of length $N$ is given. For every tuple $(i, j, k, l)$ with $1 \le i \le j < k \le l \le N$ , remove the interval $[i, j]$ and the interval $[k, l]$ from $A$ , then take the maximum of the remaining elements. Find the sum of these maxima over all valid tuples. The maximum of an empty array is assumed to be $0$ .

Input

The first line contains $N$ $(3 \le N \le 10^5)$ .

The second line contains the $N$ integers of permutation $A$ , separated by spaces. $(1 \le A_i \le N$ ; all $A_i$ are distinct. $)$

Output

Print the answer modulo $10^9+7$ .

Hint

The interval $[s, e]$ of $A$ means $A_s, A_{s+1}, \cdots, A_e$ .

Examples1

Example 1
Input
```
4
4 2 3 1
```
Expected output
```
35
```