C. Choose Two
time limit per test
4.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There is a street in your town that contains $$$N$$$ houses in a row. Each house $$$i$$$ has a height $$$H_{i}$$$.

A dome is built by selecting a continuous range of houses $$$[l, r]$$$, and its height is equal to the maximum height among them, i.e., the height $$$h$$$ of the dome is given by $$$h = \max\limits_{l \leq i \leq r}{\{H_{i}\}}$$$.

The Intrepid Construction Planning Crew wants to build exactly two non-overlapping, similar domes on the street. Two domes are similar if their heights are the same.

Compute the number of ways to choose the two domes to build modulo $$$10^{9} + 7$$$.

For example, if $$$N = 8$$$ and $$$H = \{2, 7, 4, 8, 6, 6, 6, 5\}$$$, then there are $$$9$$$ possible ways to choose the two domes:

  1. $$$\{2, 7, 4, 8, [6], [6], 6, 5\}$$$
  2. $$$\{2, 7, 4, 8, [6], [6, 6], 5\}$$$
  3. $$$\{2, 7, 4, 8, [6], [6, 6, 5]\}$$$
  4. $$$\{2, 7, 4, 8, [6], 6, [6], 5\}$$$
  5. $$$\{2, 7, 4, 8, [6], 6, [6, 5]\}$$$
  6. $$$\{2, 7, 4, 8, 6, [6], [6], 5\}$$$
  7. $$$\{2, 7, 4, 8, 6, [6], [6, 5]\}$$$
  8. $$$\{2, 7, 4, 8, [6, 6], [6], 5\}$$$
  9. $$$\{2, 7, 4, 8, [6, 6], [6, 5]\}$$$
Input

The first line of input contains an integer $$$N$$$ ($$$1 \leq N \leq 2\cdot 10^{6}$$$) — The number of houses in the street.

The second line of input contains $$$N$$$ integers $$$H_{i}$$$ ($$$1 \leq H_{i} \leq N$$$) — The $$$i$$$-th integer is the height of the $$$i$$$-th house.

Output

Print a single line — The answer to the problem.

Examples
Input
8
2 7 4 8 6 6 6 5
Output
9
Input
10
6 5 5 4 6 1 6 5 2 6
Output
248