Farmer John's Cow Organization (UCFJ) sends a delegation to the International Sheep Olympiad (IOI).
N cows participate in the delegation selection (1≤N≤2⋅10
5). They stand in a row, and cow i has breed b
i.
The delegation consists of a contiguous range of at least two cows - i.e. l…r cows for integers l and r satisfying 1≤l<r≤N. the two outer cows of the selected interval are called "leaders". To avoid conflict between breeds of cows, each leader must have a breed different from the other cows of the delegation (leaders and non-leaders).
Specify the number of ways to select a delegation.
Input:
The first line contains N.
The second line contains N integers b
1,b
2,…,b
N, each in the interval [1,N].
Output:
The number of possible delegations, on a separate line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7
1 2 3 4 3 2 5
| 13 |
Each delegation corresponds to one of the following leader pairs:
(1.2),(1.3),(1.4),(1.7),(2.3),(2.4),(3.4),(4.5),(4 ,6),(4,7),(5,6),(5,7),(6,7). |