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

Обмеження: 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] такими не є.