You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

K - 最值

题目描述

在夏令营的最后，新新为了证明这次夏令营是人生中最最最最最难忘的一段时光，他向明明出了一道题，名为——最值。

然而，明明发现这道题他好像并不会做，为了不让参加这次夏令营的大家扫兴，明明来想你求助这道题。

首先给出一个长度为 $n$ 的序列 $a(1\le a_i \le n)$ ，找到满足下列条件的二元组 $(i,j)$ 的数量：

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

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数，分别代表 $a_1 , a_2, \dots , a_n$ 。

输出格式

一个整数，代表满足题意的二元组 $(i,j)$ 的数量。

样例

输入 $1$

4
1 3 2 4

输出 $1$

2

输入 $2$

10
5 8 2 2 1 6 7 2 9 10

输出 $2$

8

数据范围

对于所有数据，保证 $1\le n \le 5\times 10^{5}$ ，$1\le a_i \le n$ 。