/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1\leq i<j<k\leq N をみたす整数の組 (i,j,k) であって、
次の条件をみたすものの個数を求めてください。
A_i,A_j,A_k の中にちょうど 2 種類の値が含まれる。すなわち、A_i,A_j,A_k の中のいずれか 2 つは等しく、残りの 1 つは異なる。
制約
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
条件をみたす整数の組の個数を出力せよ。
入力例 1
5 3 2 5 2 2
出力例 1
6
例えば、(i,j,k)=(1,2,4) は、A_1=3, A_2=2, A_4=2 の中に 2,3 のちょうど 2 種類の値が含まれるため、条件をみたします。
これを含めて、(i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) の 6 組が条件をみたします。
よって、6 を出力します。
入力例 2
3 1 1 1
出力例 2
0
条件をみたす組が存在しない可能性もあります。
Score : 300 points
Problem Statement
You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N).
Find the number of triples of integers (i,j,k) satisfying 1\leq i<j<k\leq N that satisfy the following condition:
Exactly two distinct values are contained in A_i,A_j,A_k. That is, two of A_i,A_j,A_k are equal, and the remaining one is different.
Constraints
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the number of triples of integers that satisfy the condition.
Sample Input 1
5 3 2 5 2 2
Sample Output 1
6
For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A_1=3, A_2=2, and A_4=2.
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
Therefore, print 6.
Sample Input 2
3 1 1 1
Sample Output 2
0
There may be no triples that satisfy the condition.