题目背景

译自 Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) 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
3 1 2 

3

5
3 2 1 2 3

5

7
2 1 3 1 2 3 4

8

提示

样例解释

样例 $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$。