题目描述

给定一个长度为 n 的序列 $a_{1}$,$a_{2}$,…,$a_n$。请你找出一共有多少个数对 (i,j) 满足 $a_i\lt i\lt a_j\lt j$，$1\le i,j\le n$。

例如，长度为 8 的序列 [1,1,2,3,8,2,1,4]，有 3 个满足要求的数对：(2,4)、(2,8)、(3,8)：

• 数对 (2,4) 有 $a[2]=1,a[4]=3$ 满足 $a[2]\lt 2\lt a[4]\lt 4$；
• 数对 (2,8) 有 $a[2]=1,a[8]=4$ 满足 $a[2]\lt 2\lt a[8]\lt 8$；
• 数对 (3,8) 有 $a[3]=2,a[8]=4$ 满足 $a[3]\lt 3\lt a[8]\lt 8$。

输入格式

第一行，一个整数 n；

第二行，n 个整数 $a_{1}$,$a_{2}$,…,$a_n$。

输出格式

一行，一个整数，表示满足要求的数对数目。

8
1 1 2 3 8 2 1 4

3

1
0

0

10
0 0 0 0 0 0 0 0 0 0

0

提示

数据范围

对于 100% 的数据：$1\le n\le 2\times 10^{6},0\le a_i\le 10^{9}$。