题目背景

译自 第24回日本情報オリンピック 本選 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$ 的最小值。

5
5 3 4 2 1

2

6
2 1 1 2 2 1

1

10
2 4 6 7 4 5 5 3 4 1

3

提示

样例解释

样例 $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）无额外限制。