配点 : $300$ 点

問題文

$N$ 個の整数からなる配列 $A=(A_1,A_2,...,A_N)$ が与えられるので、次の条件を全て満たす整数組 $(i,j)$ の数を求めてください。

• $1 \le i < j \le N$
• $A_i \neq A_j$

制約

• 入力は全て整数
• $2 \le N \le 3 \times 10^5$
• $1 \le A_i \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを整数として出力せよ。

3
1 7 1

2

この入力では、$A=(1,7,1)$ です。

• 整数組 $(1,2)$ に対して、$A_1 \neq A_2$ です。
• 整数組 $(1,3)$ に対して、$A_1 = A_3$ です。
• 整数組 $(2,3)$ に対して、$A_2 \neq A_3$ です。

10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

45

20
7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4

173