Вам дан массив целых чисел \(a_1, a_2, \dots a_n\). Найдите число пар индексов \(1 \leq i, j \leq n\) таких, что \(a_i < i < a_j < j\).
Выходные данные
Для каждого набора входных данных выведите одно число — количество пар индексов, удовлетворяющих неравенству из условия.
Пожалуйста, обратите внимание, что ответ для некоторых тестовых примеров может не поместиться в 32-разрядный целочисленный тип, поэтому вы должны использовать по крайней мере 64-разрядный целочисленный тип в вашем языке программирования (например, long long для C++).
Примечание
В первом наборе входных данных пары \((i, j)\) = \(\{(2, 4), (2, 8), (3, 8)\}\).
- Пара \((2, 4)\) подходит, потому что \(a_2 = 1\), \(a_4 = 3\) и \(1 < 2 < 3 < 4\).
- Пара \((2, 8)\) подходит, потому что \(a_2 = 1\), \(a_8 = 4\) и \(1 < 2 < 4 < 8\).
- Пара \((3, 8)\) подходит, потому что \(a_3 = 2\), \(a_8 = 4\) и \(2 < 3 < 4 < 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2
|
3
0
10
0
1
|