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

Limits: 2 sec., 256 MiB

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

Input

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

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

Output

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
7 6 3 4 1 2 7 5	4

Notes

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