数对数目

题目

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\ldots,a_n\)。请你找出一共有多少个数对 \((i,j)\) 满足 \(a[i] \lt i \lt a[j] \lt j\ , 1 \leqslant i, j \leqslant n\) 。
例如，长度为 \(5\) 的序列 \([1, 1, 2, 3, 8, 2, 1, 4]\)，有 \(3\) 个满足要求的数对：\((2,4)\)、\((2,8)\)、\((3,8)\)：

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

限制：

• \(1 \leqslant n \leqslant 2 \times 10^6\)
• \(0 \leqslant a_i \leqslant 10^9\)

算法分析