Підрядки-перестановки

Обмеження: 2 сек., 256 МіБ

У Марічки є перестановка $p$ цілих чисел від 1 до $n$, включно. Її цікавить такее запитання: скільки є проміжків $[l; r] (1 \le l \le r \le n)$, для яких послідовність $p[l..r]$ також є перестановкою? Допоможіть їй знайти відповідь на це запитання.

Вхідні дані

У першому рядку задано одне ціле число $n$ — кількість елементів у заданій перестановці.

У другому рядку задано $n$ цілих чисел $p_1, p_2, ..., p_n$ — перестановка Марічки.

Вихідні дані

У єдиному рядку виведіть одне ціле число — відповідь на запитання Марічки.

Обмеження

$1 \le n \le 10^5$,

для 40% тестів виконується додаткове обмеження: $n \le 10^3$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 6 3 4 1 2 7 5	4

Примітки

Перестановкою розміром $n$ називається послідовність із $n$ цілих чисел, у якій кожне із значень від 1 до $n$ входить рівно один раз. Наприклад, послідовності [3, 1, 2], [1], та [1, 2, 3, 4] є перестановками, тоді як [2], [4, 1, 2], [3, 1] такими не є.