C - Swappable Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

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

入力例 1

3
1 7 1

出力例 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 です。

入力例 2

10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

出力例 2

45

入力例 3

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

出力例 3

173

Score : 300 points

Problem Statement

Given an array of N integers A=(A_1,A_2,...,A_N), find the number of pairs (i,j) of integers satisfying all of the following conditions:

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

Constraints

  • All values in input are integers.
  • 2 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

3
1 7 1

Sample Output 1

2

In this input, we have A=(1,7,1).

  • For the pair (1,2), A_1 \neq A_2.
  • For the pair (1,3), A_1 = A_3.
  • For the pair (2,3), A_2 \neq A_3.

Sample Input 2

10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

Sample Output 2

45

Sample Input 3

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

Sample Output 3

173