P10885 【MX-S3-T1】「FeOI Round 1」野心

原题链接：。 --- 

给出一个 $1 \sim n$ 的排列 $p$，询问存在多少个数 $i$（$1 \le i

无

无

**【样例解释 #1】** 第一组：三种拆分为 $[1,3,2][4]$，$[1,3][2,4]$，$[1][3,2,4]$。 第二组：三种拆分为 $[1][5,3,2,4]$，$[1,5][3,2,4]$，$[1,5,3][2,4]$。 **【样例解释 #2】** 第一组：两种拆分为 $[2,1][4,3,6,5]$，$[2,1,4,3][6,5]$。 第二组：每种拆分都是合法的。 第三组：每种拆分都是合法的。 第四组：不存在拆分方案，故没有方案合法。 **【数据范围】** **本题开启捆绑测试。** 设 $\sum n$ 为单个测试点内所有的 $n$ 之和。 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^6$，$1 \le \sum n \le 2 \times 10^6$，保证 $p$ 是排列且 $1 \le p_i \le n$。 | 子任务编号 | $n $ | $\sum n $ | 分数 | | :-: | :-: | :-: | :-: | | $1$ | $\le 10^3$ | $\le 5\times 10^3$ | $30$ | | $2$ | $\le 10^5$ | $\le 5\times 10^5$ | $30$ | | $3$ | $\le 10^6$ | $\le 2\times 10^6$ | $40$ | **请使用较快的输入输出方式。** **新增子任务 4 为 hack 数据，分值为 $\boldsymbol{0}$。**