← 返回题目列表

Codeforces · 1083/D

D. 公平坚果变得疯狂

中文机器翻译题面 查看原题

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)$$$