codeforces#P1083D. The Fair Nut's getting crazy

The Fair Nut's getting crazy

Description

The Fair Nut has found an array aa of nn integers. We call subarray lrl \ldots r a sequence of consecutive elements of an array with indexes from ll to rr, i.e. al,al+1,al+2,,ar1,ara_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]a=[1, 2, 3, 5, 5]. Pairs (13;25)(1 \ldots 3; 2 \ldots 5) and (12;23)(1 \ldots 2; 2 \ldots 3)) — are good, but (13;23)(1 \dots 3; 2 \ldots 3) and (34;45)(3 \ldots 4; 4 \ldots 5) — are not (subsegment 131 \ldots 3 contains subsegment 232 \ldots 3, integer 55 belongs both segments, but occurs twice in subsegment 454 \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 109+710^9+7.

The first line contains a single integer nn (1n1051 \le n \le 10^5) — the length of array aa.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (109ai109-10^9 \le a_i \le 10^9) — the array elements.

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

Input

The first line contains a single integer nn (1n1051 \le n \le 10^5) — the length of array aa.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (109ai109-10^9 \le a_i \le 10^9) — the array elements.

Output

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

Samples

输入数据 1

3
1 2 3

输出数据 1

1

输入数据 2

5
1 2 1 2 3

输出数据 2

4

Note

In the first example, there is only one pair of good subsegments: (12,23)(1 \ldots 2, 2 \ldots 3).

In the second example, there are four pairs of good subsegments:

  • (12,23)(1 \ldots 2, 2 \ldots 3)
  • (23,34)(2 \ldots 3, 3 \ldots 4)
  • (23,35)(2 \ldots 3, 3 \ldots 5)
  • (34,45)(3 \ldots 4, 4 \ldots 5)