AT_joi2025ho_d.長いだけのネクタイ 2 (Just Long Neckties 2)

Just Odd Inventions Co., Ltd.（以下简称 JOI 公司）因“专做奇怪发明”而闻名遐迩。为庆祝其明星产品“超长领带”上市 5 周年，JOI 公司又推出了一款新品——“超伸缩领带”。顾名思义，这种领带最大的特点就是可以无限延长。

JOI 公司决定举办一场发布会推广新品，而你被选为了此次活动的主持人。在活动中，多名模特将身穿新款领带登上舞台。起初，每位模特脖子上的领带长度都为 $1$。

随后，你将进行共 $N$ 场“表演”来向观众展示伸缩领带的神奇功能。每一场表演按照如下流程进行：

1. 你先请观众随意喊出一个数，记为 $x$。
2. 你可以选择“响应”或“忽略”这个数。
   • 如果选择“响应”，你必须从所有领带长度小于等于 $x$ 的模特中选出一位，并将其领带长度调整为恰好 $x$。（你也可以选择本身领带长度已经为 $x$ 的模特）。如果此时没有任何一名合适的模特可选，则活动“失败”。
   • 如果选择“忽略”，你什么也不用做。

但要注意：如果你连续两次或以上选择“忽略”，观众会生气，导致活动“失败”。

至于上场展示的模特数量 $k$（$k\geq 1$），目前尚未确定。由于雇模特要花不少钱，所以你希望 $k$ 尽量小。在不给活动失败的前提下，$k$ 的最小取值由观众每场喊出的数字序列决定。幸运的是，你具有超能力，已经预知了第 $i$ 场表演时观众喊出的数字为 $A_i$。

请你编程，给定观众每一场表演的喊数 $A_1,A_2,\dots,A_N$，求防止活动失败所需的最小模特数 $k$。

阅读标准输入中的数据。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出一行，表示防止活动失败所需的最小模特数量 $k$。

子任务

1.（10 分）$N\leq 15$。
2.（6 分）$N\leq 500$，且 $A_i \leq 2$。
3.（12 分）$N\leq 500$，且 $A_i \leq 5$。
4.（18 分）$N\leq 500$，且 $A_i \leq 15$。
5.（26 分）$N\leq 500\,000$，且 $A_i \leq 15$。
6.（10 分）$N\leq 500\,000$。
7.（18 分）无额外约束。

---

样例解释 1

若 $k=2$，一次可能的活动流程如下：

• 首先，两位戴着新领带的模特登台，二者初始领带长度均为 $1$。
• 第 1 场观众喊出 $5$，你选择忽略。
• 第 2 场观众喊出 $3$，你响应，将第一位模特的领带长度调整为 $3$。此时两位模特的领带长度分别为 $3$ 和 $1$。
• 第 3 场观众喊出 $4$，你响应，将第一位模特的领带长度调整为 $4$。此时两位模特的领带长度分别为 $4$ 和 $1$。
• 第 4 场观众喊出 $2$，你响应，将第二位模特的领带长度调整为 $2$。此时两位模特的领带长度分别为 $4$ 和 $2$。
• 第 5 场观众喊出 $1$，你选择忽略。

若 $k=1$ 无论你怎么操作，总会失败。例如按上述策略操作，第 3 场过后唯一的模特领带长度为 $4$，第 4 场观众喊 $2$ 时，无法选出领带长度不大于 $2$ 的模特，对应活动失败。

因此，本例所需的最小模特数量 $k$ 为 $2$，输出应为 $2$。

此样例满足子任务 $1,3,4,5,6,7$ 的约束。

---

样例解释 2

若 $k=1$，一次可能的活动流程如下：

• 一名戴着新领带的模特出场，初始领带长度为 $1$。
• 第 1 场观众喊出 $2$，你选择忽略。
• 第 2 场观众喊出 $1$，你响应，将该模特的领带长度设置为 $1$。
• 第 3 场观众喊出 $1$，你响应，将该模特的领带长度再次设为 $1$。
• 第 4 场观众喊出 $2$，你响应，将该模特的领带长度调整为 $2$。
• 第 5 场观众喊出 $2$，你响应，将该模特的领带长度再次设为 $2$。
• 第 6 场观众喊出 $1$，你选择忽略。

注意，上述第 2、3 场其实没有改变模特长度（选了已经为 $1$ 的模特），这是允许的。

因此，本例最小所需模特数 $k$ 为 $1$，输出为 $1$。

此样例满足所有子任务的约束。

---

样例解释 3

本组样例满足子任务 $1,4,5,6,7$ 的约束。

数据范围

• $2 \leq N \leq 5\,000\,000$。
• $1 \leq A_i \leq 21\ (1 \leq i \leq N)$。
• 所有输入均为整数。

由 ChatGPT 5 翻译