Contest Duration: - (local time) (100 minutes) Back to Home
C - Min Max Pair /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

• 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


### 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