C - Min Max Pair
Editorial
/


Time Limit: 2 sec / Memory Limit: 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