Just Odd Inventions Co., Ltd. 是一家以制造“奇思妙想的发明”而闻名的公司。在这里，我们简称为 JOI 公司。

为了庆祝其旗舰产品“长领带”诞生 5 周年，JOI 公司发明了一种新产品：“可伸缩领带”。顾名思义，这种新领带具有可以无限延伸长度的独特功能。

JOI 公司决定举办一场展示活动来推广这种新领带，而你被选为活动的负责人。在活动中，几位佩戴新领带的模特将出现在舞台上。最初，每位模特佩戴的领带长度都设为 1。

之后，你将进行总共 $N$ 场表演，向观众展示领带的可伸缩功能。每场表演按如下方式进行：

1. 首先，你要求观众喊出一个他们选择的数字。设这个数字为 $x$。
2. 接下来，你决定是响应还是忽略它。
   • 如果你选择响应，你必须选择舞台上当前领带长度小于或等于 $x$ 的模特之一，并将该模特的领带长度设置为恰好 $x$。（注意，你可以选择领带长度已经是 $x$ 的模特。）但是，如果没有模特可以被选中，则展示活动失败。
   • 如果你选择忽略，则什么都不做。

然而，如果你连续两次或多次忽略观众喊出的数字，观众会感到愤怒，展示活动将失败。

舞台上的模特数量，记为 $k$ ($k \ge 1$)，尚未确定。由于雇佣模特需要花费大量资金，因此希望 $k$ 尽可能小。为防止展示活动失败所需的最小 $k$ 值取决于表演期间观众喊出的数字。幸运的是，你拥有预知能力，并预见到第 $i$ 场表演（$1 \le i \le N$）中观众喊出的数字将是 $A_i$。

编写一个程序，在给定展示活动期间观众喊出的数字的情况下，计算为防止展示活动失败所需的最小模特数量 $k$。

输入格式

从标准输入读取以下数据。

$N$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

向标准输出写入一行。输出应包含为防止展示活动失败所需的最小模特数量 $k$。

数据范围

• $2 \le N \le 5\,000\,000$。
• $1 \le A_i \le 21$ ($1 \le i \le N$)。
• 给定值均为整数。

子任务

1. (10 分) $N \le 15$。
2. (6 分) $N \le 500, A_i \le 2$ ($1 \le i \le N$)。
3. (12 分) $N \le 500, A_i \le 5$ ($1 \le i \le N$)。
4. (18 分) $N \le 500, A_i \le 15$ ($1 \le i \le N$)。
5. (26 分) $N \le 500\,000, A_i \le 15$ ($1 \le i \le N$)。
6. (10 分) $N \le 500\,000$。
7. (18 分) 无附加限制。

样例

样例输入 1

5
5 3 4 2 1

样例输出 1

2

说明

当 $k = 2$ 时，展示活动可以按如下方式进行：

• 首先，两名佩戴新领带的模特出现在舞台上。最初，每位模特的领带长度均为 1。
• 在第 1 场表演中，观众喊出 5。你忽略它。
• 在第 2 场表演中，观众喊出 3。你通过选择第一位模特并将他们的领带长度设置为 3 来响应。此时两名模特的领带长度分别为 3 和 1。
• 在第 3 场表演中，观众喊出 4。你通过选择第一位模特并将他们的领带长度设置为 4 来响应。此时两名模特的领带长度分别为 4 和 1。
• 在第 4 场表演中，观众喊出 2。你通过选择第二位模特并将他们的领带长度设置为 2 来响应。此时两名模特的领带长度分别为 4 和 2。
• 在第 5 场表演中，观众喊出 1。你忽略它。

当 $k = 1$ 时，展示活动总是会失败。例如，如果你按照上述方式在第 2、3 和 4 场表演中响应观众的数字，那么在第 3 场表演后，唯一模特的领带长度变为 4。然后，在第 4 场表演中，你无法选择领带长度小于或等于 2 的模特，因此展示活动失败。

因此，为防止展示活动失败所需的最小模特数量 $k$ 为 2，输出应为 2。

样例输入 2

6
2 1 1 2 2 1

样例输出 2

1

说明

当 $k = 1$ 时，展示活动可以按如下方式进行：

• 首先，一名佩戴新领带的模特出现在舞台上。最初，模特的领带长度为 1。
• 在第 1 场表演中，观众喊出 2。你忽略它。
• 在第 2 场表演中，观众喊出 1。你通过选择舞台上唯一的模特并将他们的领带长度设置为 1 来响应。
• 在第 3 场表演中，观众喊出 1。你通过选择舞台上唯一的模特并将他们的领带长度设置为 1 来响应。
• 在第 4 场表演中，观众喊出 2。你通过选择舞台上唯一的模特并将他们的领带长度设置为 2 来响应。
• 在第 5 场表演中，观众喊出 2。你通过选择舞台上唯一的模特并将他们的领带长度设置为 2 来响应。
• 在第 6 场表演中，观众喊出 1。你忽略它。

注意，在上面的例子中，在第 2 和第 3 场表演中，选择了领带长度已经是 1 的模特，并将他们的领带长度再次设置为 1。这种领带长度没有改变的选择也是允许的。

因此，为防止展示活动失败所需的最小模特数量 $k$ 为 1，输出应为 1。

样例输入 3

10
2 4 6 7 4 5 5 3 4 1

样例输出 3

3