P10833 [COTS 2023] Down Niz

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T2。$\texttt{1s,0.5G}$。 Happy birthday to NaCly_Fish!（2024.7.28）。

Given a sequence $a$ of length $N$, find the number of pairs $(l,r)$ that satisfy the following conditions: - $1\le l\le r\le N$； - $a_l,a_{l+1},\cdots,a_{r-1},a_r$ is a permutation of $1\sim r-l+1$。

The first line contains a positive integer $N$, representing the length of the sequence. The second line contains $N$ positive integers describing the sequence $a$。

Output one integer in a single line, the number of pairs $(l,r)$ that satisfy the conditions.

### Sample Explanation Explanation for Sample $3$: the pairs $(l,r)$ that satisfy the conditions are $(2,2),(1,2),(1,3),(4,4),(4,5),(4,6),(4,7),(3,5)$。 #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1\le N\le 10^6$； - $1\le a_i\le N$。 | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $13$ | Each number appears exactly once in the sequence. | | $2$ | $20$ | $N\le 5\, 000$ | | $3$ | $33$ | $N\le 50\, 000$ | | $4$ | $34$ | No additional constraints. | Translated by ChatGPT 5