给定长度为 $n$ 的序列 $a$，求最少将其划分为多少个子序列，使得划分出的每个子序列中相邻两项之差的绝对值均为 $1$。

数据范围：多测，$\sum n\le 10^6$，值域 $[1,2n]$。

考虑建图，即每个点向编号比它大且差的绝对值为 $1$ 的所有点连边，这时原题变成了最小路径覆盖。DAG 最小路径覆盖一般要转化为二分图最大匹配。

但本题是 $10^6$ 显然直接匈牙利需要大约 $31.71$ 年（不考虑闰年），所以我们要考虑优化。

由于二分图是无向图，所以连边的方式可以改为每个 $i$ 向所有 $a_j=a_i+1$ 的 $j$ 连边，二分图是不变的。

然后发现此时按 $a_i$ 从小往大匹配一定是不劣的。于是这题就变成从小往大枚举 $a_i$ 并尽可能匹配 $a_i+1$ 然后就做到线性（或者 $1\log$，视实现而定）了。