7157: ABC252 —— D - Distinct Trio
[Creator : ]
Description
You are given a sequence of length $N: A=(A_1,A_2,\ldots,A_N)$.
Find the number of triples (i,j,k) that satisfy both of the following conditions.
Find the number of triples (i,j,k) that satisfy both of the following conditions.
- $1\leq i \lt j \lt k \leq N$
- $A_i, A_j$, and $A_k$ are distinct.
Input
Input is given from Standard Input in the following format:
$N$
$A_1\ A_2\ \ldots\ A_N$
$N$
$A_1\ A_2\ \ldots\ A_N$
Output
Print the answer.
Constraints
$3≤N≤2×10^5$
$1 \leq A_i \leq 2\times 10^5$
All values in input are integers.
$1 \leq A_i \leq 2\times 10^5$
All values in input are integers.
Sample 1 Input
4
3 1 4 1
Sample 1 Output
2
The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).
Sample 2 Input
10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990
Sample 2 Output
120
Sample 3 Input
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Sample 3 Output
355