Problem Description

Xiaoming has been thinking about a strange but interesting problem these days:

In a certain permutation of $1$ to $N$, how many consecutive-number intervals are there? The definition of a consecutive-number interval is:

If all elements in the interval $[L, R]$ (that is, the $L$-th to the $R$-th elements of the permutation), after being sorted in increasing order, form a "consecutive" sequence of length $R - L + 1$, then this interval is called a consecutive-number interval.

The definition of a "consecutive" sequence is:

For a sequence $A$ of length $m$, let its $i$-th element be $A_i$. If $\forall i \in [2,m]$, $A_i = A_{i-1} + 1$, then the sequence is considered "consecutive".

When $N$ is very small, Xiaoming can quickly compute the answer. But when $N$ becomes large, the problem is not so simple. Now Xiaoming needs your help.

Input Format

The first line contains a positive integer $N$ $(1 \le N \le 50000)$, indicating the size of the permutation.

The second line contains $N$ distinct numbers $P_i$ $(1 \le P_i \le N)$, representing a permutation of these $N$ numbers.

Output Format

Output an integer, representing the number of different consecutive-number intervals.

4
3 2 4 1

7

5
3 4 2 5 1

9

Hint

In the first sample, there are $7$ consecutive-number intervals: $[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[2,2]$, $[3,3]$, $[4,4]$.

In the second sample, there are $9$ consecutive-number intervals: $[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[1,5]$, $[2,2]$, $[3,3]$, $[4,4]$, $[5,5]$.

Original time limit: 5 seconds, 64 MB. Lanqiao Cup 2013, the 4th Provincial Contest.

Translated by ChatGPT 5