I. И опять перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность Ai, состоящая из N целых чисел. Найдите количество таких пар (L, R), для которых подотрезок {AL, AL + 1, ..., AR} является перестановкой из R - L + 1 чисел. Перестановкой из K чисел называется любая последовательность чисел от 1 до K, в которой каждый элемент встречается ровно один раз.

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

В первой строке содержится число N  — длина последовательности. Во второй строке содержатся N целых чисел  — последовательность Ai.

1 ≤ N ≤ 106
1 ≤ Ai ≤ N
Выходные данные

В единственной строке выведите одно число — количество пар (L, R), удовлетворяющим заданным условиям.

Пример
Входные данные
3
3 1 2
Выходные данные
3