题解：CF2165F Arctic Acquisition

显然 $[l,r]$ 合法一定有 $[l-1,r],[l,r+1]$ 合法，这样求出来每个 $l$ 最小的 $r$ 合法即可，答案为 $\sum n-f_i+1$。

注意到子序列 $21435$ 显然要拆开。固定 $2$ 的位置 $i$，一定是找下一个 $a_j<a_i,j>i$ 作为 $1$。放到坐标系 $(i,a_i)$ 上，转化为 $x\in[j+1,n],y\in[a_i+1,n]$ 的部分中的一个 $213$ 子序列，范围即为一个 2-side 矩形。

考虑枚举这个子序列中 $1$ 的位置 $p$，注意枚举 $2$ 的话这里就会有很多 $(2,1,3)$，考虑枚举 $3$ 的位置 $q$，如果并非 $[p+1,n]$ 中的前缀 $\max$ 那么就会被前面那个点支配掉。令 $[p+1,n]$ 中所有前缀 $\max$ 并且 $>a_p$ 的位置分别为 $r_1,r_2,r_3,\cdots$。如果最终取的是 $r_2,r_3$ 之类，那么取的 $2$ 的值一定 $>a_{r_1}$，那么 $p$ 可以移动到 $r_1$，并且范围更大，因此只需要考虑 $a_{r_1}$ 为 $3$。对于 $r_1$ 显然可以用单调栈找。此时找前缀最后一个落在 $[a_p,a_{r_1}]$ 的点作为 $2$ 即可。综上，只有 $\mathcal O(n)$ 个有效的 $213$ 子序列。

转化为：$n$ 个带点权的点，查询的是 $n$ 个 2-side 矩形内部点权 $\min$。容易扫描线解决，时间复杂度 $\mathcal O(n\log n)$。