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.

题目描述

题目译自 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)$。
• 输入的所有值均为整数。

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