P10833 [COTS 2023] 下 Niz

译自 [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T2。$\texttt{1s,0.5G}$。 祝 NaCly_Fish 生日快乐！（2024.7.28）

给定长度为 $N$ 的序列 $a$，求满足以下条件的 $(l,r)$ 对数： - $1\le l\le r\le N$； - $a_l,a_{l+1},\cdots,a_{r-1},a_r$ 是 $1\sim r-l+1$ 的排列。

第一行，一个正整数 $N$，表示序列长度； 第二行，$N$ 个正整数，描述序列 $a$。

一行一个整数，即满足条件的 $(l,r)$ 的数量。

### 样例解释 样例 $3$ 解释：满足条件的 $(l,r)$ 有 $(2,2),(1,2),(1,3),(4,4),(4,5),(4,6),(4,7),(3,5)$。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le N\le 10^6$； - $1\le a_i\le N$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $13$ | 每个数只在序列中出现一次 | | $2$ | $20$ | $N\le 5\, 000$ | | $3$ | $33$ | $N\le 50\, 000$ | | $4$ | $34$ | 无额外约束 |