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

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] такими не є.