P8600 [Lanqiao Cup 2013 NOI Qualifier B] Number of Consecutive-Number Intervals

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.

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 an integer, representing the number of different consecutive-number intervals.

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