You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 第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）无额外限制。