The Fair Nut's getting crazy

题意翻译

给定一个长度为 $n$ 的序列 $\{a_i\}$。你需要从该序列中选出两个非空的子段，这两个子段满足： - 两个子段非包含关系。 - 两个子段存在交。 - 位于两个子段交中的元素在每个子段中只能出现一次。 求共有多少种不同的子段选择方案。输出总方案数对 $10^9 + 7$ 取模后的结果。 需要注意的是，选择子段 $[a, b]$、$[c, d]$ 与选择子段 $[c, d]$、$[a, b]$ 被视为是相同的两种方案。 $1 \leq n \leq 10^5, -10^9 \leq a_i \leq 10^9$。

题目描述

The Fair Nut has found an array $ a $ of $ n $ integers. We call subarray $ l \ldots r $ a sequence of consecutive elements of an array with indexes from $ l $ to $ r $ , i.e. $ a_l, a_{l+1}, a_{l+2}, \ldots, a_{r-1}, a_{r} $ . No one knows the reason, but he calls a pair of subsegments good if and only if the following conditions are satisfied: 1. These subsegments should not be nested. That is, each of the subsegments should contain an element (as an index) that does not belong to another subsegment. 2. Subsegments intersect and each element that belongs to the intersection belongs each of segments only once. For example $ a=[1, 2, 3, 5, 5] $ . Pairs $ (1 \ldots 3; 2 \ldots 5) $ and $ (1 \ldots 2; 2 \ldots 3) $ ) — are good, but $ (1 \dots 3; 2 \ldots 3) $ and $ (3 \ldots 4; 4 \ldots 5) $ — are not (subsegment $ 1 \ldots 3 $ contains subsegment $ 2 \ldots 3 $ , integer $ 5 $ belongs both segments, but occurs twice in subsegment $ 4 \ldots 5 $ ). Help the Fair Nut to find out the number of pairs of good subsegments! The answer can be rather big so print it modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the array elements.

输出格式

Print single integer — the number of pairs of good subsegments modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

1

输入样例 #2

5
1 2 1 2 3

输出样例 #2

4

说明

In the first example, there is only one pair of good subsegments: $ (1 \ldots 2, 2 \ldots 3) $ . In the second example, there are four pairs of good subsegments: - $ (1 \ldots 2, 2 \ldots 3) $ - $ (2 \ldots 3, 3 \ldots 4) $ - $ (2 \ldots 3, 3 \ldots 5) $ - $ (3 \ldots 4, 4 \ldots 5) $