Fair Nut 发现了一个由 $$$n$$$ 整数组成的数组 $$$a$$$。我们将子数组 $$$l \ldots r$$$ 称为数组的连续元素序列,索引从 $$$l$$$ 到 $$$r$$$,即 $$$a_l, a_{l+1}, a_{l+2}, \ldots, a_{r-1}, a_{r}$$$。
没有人知道原因,但他称一对子段是好的当且仅当满足以下条件时:
1. 这些子段不应嵌套。也就是说,每个子段应该包含不属于另一个子段的元素(作为索引)。
2. 子线段相交,属于交集的每个元素仅属于每个线段一次。
例如 $$$a=[1, 2, 3, 5, 5]$$$。对 $$$(1 \ldots 3; 2 \ldots 5)$$$ 和 $$$(1 \ldots 2; 2 \ldots 3)$$$) — 很好,但 $$$(1 \dots 3; 2 \ldots 3)$$$ 和 $$$(3 \ldots 4; 4 \ldots 5)$$$ — 不是(子段$$$1 \ldots 3$$$ 包含子段$$$2 \ldots 3$$$,整数$$$5$$$ 属于这两个段,但在子段$$$4 \ldots 5$$$ 中出现两次。
帮助公平坚果找出好子段的对数!答案可能相当大,所以打印它对 $$$10^9+7$$$ 取模。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组元素。
输出
打印单个整数 - 良好子段对的数量以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 1 2 3
输出 #1
1
输入 #2
5 1 2 1 2 3
输出 #2
4
注意
在第一个示例中,只有一对好的子段:$$$(1 \ldots 2, 2 \ldots 3)$$$。
在第二个示例中,有四对好的子段:
- $$$(1 \ldots 2, 2 \ldots 3)$$$
- $$$(2 \ldots 3, 3 \ldots 4)$$$
- $$$(2 \ldots 3, 3 \ldots 5)$$$
- $$$(3 \ldots 4, 4 \ldots 5)$$$