时间限制： 1 秒
内存限制： 512 MB

题目描述

Sasha 在学习数据结构，其中一个常见问题是区间最大值查询：给定数组 $a_1,a_2,\ldots,a_n$，回答区间 $[i,j]$ 中的最大值。

他注意到，不同区间的最大值经常相同。现在他想知道，有多少种方法可以选择一对互不重叠的区间，使得两个区间的最大值相等。

请计算满足以下条件的四元组 $(i,j,k,l)$ 的数量：

$$1 \le i \le j < k \le l \le n,$$

且

$$\max(a_i,a_{i+1},\ldots,a_j)=\max(a_k,a_{k+1},\ldots,a_l).$$

答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$，表示数组长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

约束：

• $2 \le n \le 100000$；
• $1 \le a_i \le 10^9$。

输出格式

输出互不重叠且最大值相等的区间对数量，对 $10^9+7$ 取模。

样例 1 输入

6
3 3 4 4 3 2

样例 1 输出

16

样例 2 输入

12
1 3 2 3 4 1 3 4 3 2 2 5

样例 2 输出

177