Permutation Substrings

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka has a permutation \(p\) of integers from 1 to \(n\), inclusive. She is interested in the following question: how many segments \([l; r]\) (\(1 \le l \le r \le n\)) are there, for which the sequence \(p[l..r]\) is also a permutation? Help her find the answer to this question.

Input

The first line contains a single integer \(n\) — the number of elements in the given permutation.

The second line contains \(n\) integers \(p_1, p_2, ..., p_n\) — Marichka’s permutation.

Output

In a single line, print a single integer — the answer to Marichka’s question.

Constraints

\(1 \le n \le 10^5\),

for 40% of the tests, an additional constraint holds: \(n \le 10^3\).

Samples

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

Notes

A permutation of size \(n\) is a sequence of \(n\) integers in which each value from 1 to \(n\) appears exactly once. For example, the sequences [3, 1, 2], [1], and [1, 2, 3, 4] are permutations, while [2], [4, 1, 2], [3, 1] are not.