C - Min Max Pair 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 a = (a_1, \dots, a_N) が与えられます。

以下の条件を全て満たす整数 i, j の組の総数を求めてください。

  • 1 \leq i \lt j \leq N
  • \min(a_i, a_j) = i
  • \max(a_i, a_j) = j

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq N \, (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

4
1 3 2 4

出力例 1

2

(i, j) = (1, 4), (2, 3) が条件を満たします。

入力例 2

10
5 8 2 2 1 6 7 2 9 10

出力例 2

8

Score : 300 points

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

  • 1 \leq i \lt j \leq N
  • \min(a_i, a_j) = i
  • \max(a_i, a_j) = j

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq N \, (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8