P11665 [JOI 2025 Final] 只不过是长的领带 2 / Just Long Neckties 2

译自 [第24回日本情報オリンピック 本選](https://contests.ioi-jp.org/joi-ho-2025/index.html) T4。

有一个长度为 $k$（$k\ge 1$）的正整数数列 $B_1,\cdots,B_k$，初始 $B_i=1$（$1\le i\le k$）。这里，$k$ 是一个还未确定的数。 有 $N$ 场演出，第 $i$（$1\le i\le N$）场演出中，观众将会报出数字 $A_i$。然后你需要做以下的事情： - 选择是否回应这个观众。 - 如果选择回应，你需要选择 $j$（$1\le j\le k$）满足 $B_j\le A_i$，然后令 $B_j\gets A_i$。（注意这里是小于等于号。） - 如果无法选择这样的 $j$，则演出失败。 - 否则，不需要做任何事。 然而，如果连续两次（或者更多次）选择不回应观众，观众会生气，从而演出失败。 在演出不失败的前提下，确定 $k$ 的最小值。

如下所示： > $N$ \ > $A_1$ $A_2$ $\cdots$ $A_N$

输出一行一个正整数，表示满足条件的 $k$ 的最小值。

### 样例解释 #### 样例 $1$ 解释 $k=2$ 时，在五次演出中分别选择： - 不回应； - 回应，$j=1$（此后 $B_1\gets 3$）； - 回应，$j=1$（此后 $B_1\gets 4$）； - 回应，$j=2$（此后 $B_2\gets 2$）； - 不回应； 可以证明 $k=1$ 时演出必定失败。所以输出 $2$。 该样例满足子任务 $1,3\sim 7$ 的限制。 #### 样例 $2$ 解释 $k=1$ 时，在第 $1,6$ 个演出时选择不回应即可。 该样例满足所有子任务的限制。 #### 样例 $3$ 解释 该样例满足子任务 $1,4\sim 7$ 的限制。 ### 数据范围 - $2\le N\le 5\times 10^6$。 - $1\le A_i\le 21$（$1\le i\le N$）。 - 输入的值全部是整数。 ### 子任务 1. （10pts）$N\le 15$。 2. （6pts）$N\le 500$，$A_i\le 2$（$1\le i\le N$）。 3. （12pts）$N\le 500$，$A_i\le 5$（$1\le i\le N$）。 4. （18pts）$N\le 500$，$A_i\le 15$（$1\le i\le N$）。 5. （26pts）$N\le 5\times 10^5$，$A_i\le 15$（$1\le i\le N$）。 6. （10pts）$N\le 5\times 10^5$。 7. （18pts）无额外限制。