解题思路

对于一个长度为 $k$ 的子数组，若它的 $\text{mex} \ge x$ ，说明它必须包含所有数 $0,1,\dots,x-1$ 。

由于原数组是 $0$ 到 $n-1$ 的排列，每个数只出现一次。设包含 $0,1,\dots,x-1$ 这些数的位置最左为 $L$ ，最右为 $R$ ，那么任意子数组想要包含这些数，长度至少需要：

R-L+1

题目内容

给定长度为 $n$ 的排列 $\{a_1,a_2,\dots,a_n\}$ ，对 $1 \le k \le n$ 定义

f(k) = \max_{i=1}^{n-k+1}\left(\text{mex}(a_i,a_{i+1},\dots,a_{i+k-1})\right)

求区间 $[1,n-1]$ 中有多少 $k$ 满足 $f(k) = f(k+1)$ 。

$\text{mex}$ 是没有出现在数组中的最小非负整数；长度 $n$ 的排列是由 $0,1,\dots,n-1$ 按任意顺序构成的数组（每个值恰好出现一次）。

第一行包含整数 $n$ （ $2 \le n \le 10^5$ ）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $0 \le a_i \le n-1$ ）。

一个整数，表示满足条件的 $k$ 的个数。

输入

5
2 3 1 0 4

输出

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析