Counting Moo Subsequences

Farmer John wants to explain his favorite part of the USACO contest to Elsie. He describes that his favorite part is when Bessie shouts "It's moo time" and moos continuously throughout the contest. The contest is represented as an array of N integers, a₁, a₂, ..., a_N (1 ≤ a_i ≤ N). Farmer John defines a moo as an array of three integers [x, y, y] where the second integer equals the third, but is different from the first (i.e. x ≠ y). A moo is said to occur in the contest if it is possible to remove some of the integers from the contest array (preserving the order) so that only the moo remains.

Your task is to help Elsie count the number of distinct moos that occur in the contest. Two moos are considered distinct if they are not composed of the same integers in the same order.

The mathematical formulation: You are given an array \(a_1,a_2,\dots,a_N\). A moo is a triple \((x,y,y)\) with \(x \neq y\). This moo is considered to occur if there exist indices \(i < j < k\) such that \(a_i=x,\;a_j=a_k=y\). Count the number of distinct pairs \((x,y)\) for which such a triple exists.

Note: In any valid moo with value \(y\), there must be at least two occurrences of \(y\) in the array. For each such \(y\), let \(j\) be the index of its second occurrence. Then any integer \(x\) (x \neq y) that appears in any position before index \(j\) can form a valid moo \((x,y,y)\). Therefore, for each number \(y\) that appears at least twice at indices \(i_1, i_2, \dots\) (with \(i_2\) being the second occurrence), the number of new moo sequences using \(y\) is \(D(i_2-1)-1\), where \(D(i_2-1)\) is the number of distinct integers in the subarray \(a_1, a_2, \dots, a_{i_2-1}\).

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 10^6\)), the number of integers in the contest array.

The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le N\)).

outputFormat

Output a single integer, the number of distinct moos that occur in the contest.

sample

3
1 2 1

1