United Cows of Farmer John (Gold)#11237
The United Cows of Farmer John (UCFJ) are sending a delegation to the International bOvine olympIad (IOI).
There are cows participating in delegation selection. They are standing in a line, and cow has breed b_i.
The delegation will consist of a contiguous interval of at least two cows - that is, cows l \ldots r for integers and satisfying 1 \le l < r \le n. The two outermost cows of the chosen interval will be designated as "leaders". To avoid intra-breed conflict, every leader must be of a different breed from the rest of the delegation (leaders or not).
Help the UCFJ determine (for tax reasons) the number of ways they might choose a delegation to send to the IOI.
The first line contains (1 \le n \le 2 \cdot 10^5).
The second line contains integers b_1, b_2, \ldots, b_n, each in the range .
Print the number of possible delegations, on a single line.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
Each delegation corresponds to one of the following pairs of leaders:
, , , , , , , , , , , , .
Example 1