Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Yêu Cầu: Bạn hãy đếm cặp \((i,j)\) thỏa mãn tất cả các điều kiện sau:

• \(1 \le i < j \le n\).
• \(\min(a_i,a_j) = i\).
• \(\max(a_i,a_j) = j\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa dãy số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 3 2 4

2