A delegation (1≤N≤2⋅10
5) is selected from N cows. They stand in a row, cow i has breed b
i.
The delegation will consist of a continuous segment of at least three cows, i.e. cows l…r for integers l and r satisfying the conditions 1≤l<r≤N and r−l≥2. Three cows in the selected interval are marked as leaders of the delegation. Two boundary cows must be leaders. In addition, each leader must have a different breed from all other cows in the delegation (leaders or non-leaders).
Determine the number of ways in which a delegation can be selected. Two delegations are considered different if they have different members or leaders.
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 one line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7
1 2 3 4 3 2 5
| 9 |
Each delegation corresponds to one of the following leader triplets:
(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4 ,5,7),(4,6,7),(5,6,7). |