Задача №111278. RPQ (Range Permutation Query)
От некоторых школ в командной олимпиаде по информатике участвует очень много команд. Учитель одной из таких школ раздал для регистрации своим командам номера: 1, 2, 3 и т. д. Для того чтобы проверить, все ли команды зарегистрировались, учитель выписал из таблицы регистрации только номера команд своей школы, но в том порядке, в котором команды регистрировались.
После нелёгких подсчётов оказалось, что зарегистрировались все. Но в процессе решения этой задачи учитель сформулировал следующую: сколькими способами можно выбрать стоящие подряд в этом списке K номеров команд, чтобы они образовывали некоторую перестановку чисел от 1 до K? Например, если от школы участвуют всего три команды, то при порядке регистрации 3 1 2 таких способов будет три (для K = 1, 2, 3), а при регистрации в порядке 2 3 1 — всего два (для K = 1 и K = 3).
В первой строке входных данных находится одно число N (1 ≤ N ≤ 200) — количество команд, участвующих в олимпиаде от этой школы. Во второй строке находятся N натуральных чисел от 1 до N в том порядке, в котором команды регистрировались на олимпиаду.
Гарантируется, что каждое число встречается в этой строке ровно один раз.
Выведите одно число, обозначающее число способов выбрать из списка несколько стоящих подряд команд, удовлетворяющих условию задачи.
3
2 3 1
2