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:
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.
Print a single line — The answer to the problem.
8 2 7 4 8 6 6 6 5
9
10 6 5 5 4 6 1 6 5 2 6
248
Name |
---|