Вам задана перестановка p длины n. Также вам задано m враждебных пар (ai, bi) (1 ≤ ai, bi ≤ n, ai ≠ bi).
Ваша задача посчитать количество различных интервалов (x, y) (1 ≤ x ≤ y ≤ n), которые не содержат никакие враждебные пары. Таким образом, вам не нужно считать интервалы (x, y), содержащие хотя бы одну враждебную пару (позиции и порядок значений из враждебной пары не имеют значения).
Рассмотрим пример: p = [1, 3, 2, 4] и пары {(3, 2), (4, 2)} являются враждебными. Интервал (1, 3) не является корректным, поскольку содержит враждебную пару (3, 2). Интервал (1, 4) также не является корректным, поскольку содержит две враждебные пары (3, 2) и (4, 2). Но интервал (1, 2) является корректным, поскольку не содержит враждебных пар.
Выходные данные
Выведите одно целое число c — количество различных интервалов (x, y), не содержащих враждебных пар.
Обратите внимание, что ответ может не поместиться в 32-битном типе данных. Для сохранения числа вы можете использовать, например, тип long long в языке C++ или тип long в языке Java.
Примечание
В первом примере, следующие интервалы являются корректными: (1, 1), (1, 2), (2, 2), (3, 3) и (4, 4).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3 2 4
3 2
2 4
|
5
|
|
2
|
9 5
9 7 2 3 1 4 6 5 8
1 6
4 5
2 7
7 2
2 7
|
20
|