题目描述

题目译自 JOI 2025 Final T4 「長いだけのネクタイ 2 / Just Long Neckties 2」

Just Odd Inventions 公司以发明「仅仅奇怪的东西（just odd inventions）」而闻名。这里简称为 JOI 公司。

为了纪念其畅销产品「仅仅长的领带」上市五周年，JOI 公司开发了一款全新的「无限长的领带」。这种新型领带的特点是可以无限延长。

JOI 公司决定举办一个发布会来宣传这款新型领带，并邀请你担任主持人。在发布会上，几位穿着新型领带的模特将会登台亮相。最初，每位模特的领带长度都是 $1$。

随后，你需要进行 $N$ 次表演，让观众亲身体验领带长度可调的功能。每次表演按照以下步骤进行：

1. 首先，观众说出一个他们喜欢的数字，我们称这个数字为 $x$。
2. 然后，你可以选择回应或者忽略这个数字。
   • 如果你选择回应，你需要从登台的模特中选择一个领带长度不超过 $x$ 的模特，并将其领带长度调整为 $x$（注意，选择的模特的领带长度可以已经是 $x$）。如果没有一个合适的模特可以选择，发布会将失败。
   • 如果你选择忽略，你什么也不做。 但是，如果连续两次或以上忽略观众说出的数字，观众会不满意，发布会将失败。

登台的模特数量 $k$ $(k \geq 1)$ 尚未决定，但由于雇用模特需要花费，$k$ 越小越好。为了避免发布会失败，需要的模特数量取决于每次表演中观众说出的数字。你可以预见在第 $i$ $(1 \leq i \leq N)$ 次表演中，观众会说出的数字是 $A_i$。

编写一个程序，在给定发布会中观众会说出的数字信息时，计算出避免发布会失败所需的最小模特数量 $k$。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots A_N$。

输出格式

输出避免发布会失败所需的最小模特数量 $k$。

5
5 3 4 2 1

2

当 $k=2$ 时，可以按照以下方式进行发布会：

• 首先，穿着新型领带的两位模特登台。最初，每位模特的领带长度都是 $1$。
• 第一次表演时，观众说出数字 $5$。你忽略这个数字。
• 第二次表演时，观众说出数字 $3$。你回应这个数字，并将第一位模特的领带长度调整为 $3$。此时，两位模特的领带长度分别为 $3$ 和 $1$。
• 第三次表演时，观众说出数字 $4$。你回应这个数字，并将第一位模特的领带长度调整为 $4$。此时，两位模特的领带长度分别为 $4$ 和 $1$。
• 第四次表演时，观众说出数字 $2$。你回应这个数字，并将第二位模特的领带长度调整为 $2$。此时，两位模特的领带长度分别为 $4$ 和 $2$。
• 第五次表演时，观众说出数字 $1$。你忽略这个数字。

如果 $k=1$，发布会必将失败。例如，如果按照上述方式在第二、三、四次表演中回应观众说出的数字，那么在第三次表演结束时，唯一登台的模特的领带长度将是 $4$。在第四次表演时，没有模特的领带长度不超过 $2$，因此发布会将失败。

因此，避免发布会失败所需的最小模特数量为 $2$。

这个样例满足子任务 $1,3,4,5,6,7$ 的限制。

6
2 1 1 2 2 1

1

当 $k=1$ 时，可以按照以下方式进行发布会：

• 首先，穿着新型领带的一位模特登台。最初，模特的领带长度是 $1$。
• 第一次表演时，观众说出数字 $2$。你忽略这个数字。
• 第二次表演时，观众说出数字 $1$。你回应这个数字，并将登台模特的领带长度调整为 $1$。
• 第三次表演时，观众说出数字 $1$。你回应这个数字，并将登台模特的领带长度调整为 $1$。
• 第四次表演时，观众说出数字 $2$。你回应这个数字，并将登台模特的领带长度调整为 $2$。
• 第五次表演时，观众说出数字 $2$。你回应这个数字，并将登台模特的领带长度调整为 $2$。
• 第六次表演时，观众说出数字 $1$。你忽略这个数字。

因此，避免发布会失败所需的最小模特数量为 $1$。

这个样例满足所有子任务的限制。

10
2 4 6 7 4 5 5 3 4 1

3

这个样例满足子任务 $1,4,5,6,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5000000$。
• $1 \leq A_i \leq 21$ $(1 \leq i \leq N)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$10$	$N \leq 15$
$2$	$6$	$N \leq 500, A_i \leq 2\,(1 \leq i \leq N)$
$3$	$12$	$N \leq 500, A_i \leq 5\,(1 \leq i \leq N)$
$4$	$18$	$N \leq 500, A_i \leq 15\,(1 \leq i \leq N)$
$5$	$26$	$N \leq 500000, A_i \leq 15\,(1 \leq i \leq N)$
$6$	$10$	$N \leq 500000$
$7$	$18$	无附加限制