United Cows of Farmer John (Platinum)#11240
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 three cows — that is, cows for integers and satisfying 1 \le l < r \le n and r − l \ge 2. Three of the cows in the chosen interval are marked as delegation leaders. For legal reasons, the two outermost cows of the chosen interval must be leaders. Moreover, 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. Two delegations are considered different if they have different members or different leaders.
The first line contains the number of the cows n~(1 \le n \le 2 \cdot 10^5).
The second line contains integers b_1, b_2, \ldots, b_n~(1 \le b_i \le n).
Print the number of possible delegations.
Each delegation corresponds to one of the following triples of leaders:
(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).
Example 1