Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

У вас есть массив $$$a_1, a_2, \dots, a_n$$$.

Назовем подотрезок $$$a_l, a_{l + 1}, \dots , a_r$$$ этого массива подперестановкой если он содержит все числа от $$$1$$$ до $$$r-l+1$$$ ровно по одному разу. Например, массив $$$a = [2, 2, 1, 3, 2, 3, 1]$$$ содержит $$$6$$$ подотрезков, являющихся подперестановками: $$$[a_2 \dots a_3]$$$, $$$[a_2 \dots a_4]$$$, $$$[a_3 \dots a_3]$$$, $$$[a_3 \dots a_5]$$$, $$$[a_5 \dots a_7]$$$, $$$[a_7 \dots a_7]$$$.

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

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

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ чисел $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$).

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

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

В единственной строке выведите количество подперестановок массива $$$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]$$$.