Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F. Количество подперестановок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив a1,a2,,an.

Назовем подотрезок al,al+1,,ar этого массива подперестановкой если он содержит все числа от 1 до rl+1 ровно по одному разу. Например, массив a=[2,2,1,3,2,3,1] содержит 6 подотрезков, являющихся подперестановками: [a2a3], [a2a4], [a3a3], [a3a5], [a5a7], [a7a7].

Вам нужно посчитать количество подперестановок.

Входные данные

Первая строка содержит число n (1n3105).

Вторая строка содержит n чисел a1,a2,,an (1ain).

Этот массив может содержать одинаковые числа.

Выходные данные

В единственной строке выведите количество подперестановок массива a.

Примеры
Входные данные
8
2 4 1 3 4 2 1 2
Выходные данные
7
Входные данные
5
1 1 2 1 2
Выходные данные
6
Примечание

В первом тестовом примере 7 подперестановок: [1,4], [3,3], [3,6], [4,7], [6,7], [7,7] и [7,8].

Во втором тестовом примере 6 подперестановок: [1,1], [2,2], [2,3], [3,4], [4,4] и [4,5].