← 返回题目列表

AtCoder · joi2025ho_d

D. 只是长领带 2

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

Just Odd Inventions Co., Ltd. 是一家以“Just odd Inventions”而闻名的公司。 这里我们简称为JOI公司。

为了庆祝其旗舰产品“Just Long Neckties”问世五周年,JOI 公司发明了一款新产品:“Just Stretchable Neckties”。 顾名思义,这款新型领带具有能够无限延长长度的独特功能。

JOI公司决定举办一场展示活动来推广新款领带,您已被选为该活动的主持人。 活动现场,多位佩戴新款领带的模特将出现在舞台上。 最初, 长度 模特佩戴的每条领带的 设置为 1.

之后,您将总共执行 N 表演 向观众展示领带的可拉伸特性。 每场表演的进行如下:

  1. 首先,你要求观众说出他们选择的数字。 令这个数字为 x.
  2. 接下来,您决定是否回应或忽略它。
    • 如果您选择回应,则必须选择舞台上当前领带长度为的模特之一 小于或等于 x 并将该模特领带的长度精确设置为 x。 (请注意,您可以选择领带长度已经是的型号 x。) 但是,如果无法选择模特,则展示活动将失败。
    • 如果您选择忽略它,则您什么也不做。

但是,如果连续两次或多次忽略观众的数字,观众就会生气,展示活动就会失败。

舞台上的模型数量,表示为 k (k\geq 1),尚未确定。 由于招聘模式需要花费大量资金,因此最好保留 k 尽可能小。 的最小值 防止展示活动失败所需的 k 取决于表演期间观众喊出的数字。 还好你有预知能力,预见到了观众喊出的数字。 i-次性能(1\leq i\leq N)将是 A_i.

编写一个程序,根据展示活动期间观众喊出的数字,计算模型的最小数量 需要 k 来防止展示活动失败。


输入

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

N
A_1 A_2 \cdots A_N

输出

将一行写入标准输出。 输出应包含最少数量的模型 k 来防止展示活动失败。


约束

  • 2 \leq N \leq 5\,000\,000.
  • 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 500\,000, A_i \leq 15 (1 \leq i \leq N).
  6. (10 点) N\leq 500\,000.
  7. (18 点)没有额外的限制。

示例输入 1

5
5 3 4 2 1

示例输出 1

2

当 k=2,展示活动可以按如下方式进行,例如:

  • 首先,两位佩戴新领带的模特登上舞台。最初,每个模特的领带长度是 1.
  • 第一场演出时,观众大喊 5。你忽略这一点。
  • 第二场演出时,观众大喊 3。您可以通过选择第一个模型并将其领带长度设置为来对此做出响应 3。现在两个型号的领带长度是 3 和 1。
  • 第三场演出时,观众大喊 4。您可以通过选择第一个模型并将其领带长度设置为来对此做出响应 4。现在两个型号的领带长度是 4 和 1。
  • 第四场演出时,观众大喊 2。您可以通过选择第二个模型并将其领带长度设置为来对此做出响应 2。现在两个型号的领带长度是 4 和 2。
  • 第五场公演时,观众大喊 1。你忽略这一点。

当 k=1,展示活动总是会失败。 例如,如果您在第 2、3、4 场表演中按照上述方式回复观众人数,则唯一模特的领带长度将变为 4 第三次演出后。 那么,在第4次演出时,不能选择领带长度小于或等于的模特 2,因此展示活动失败。

因此,模型的最小数量 防止展示活动失败所需的 k 是 2,输出应该是 2.

此示例输入满足子任务的约束 1,3,4,5,6, 和 7.


示例输入 2

6
2 1 1 2 2 1

示例输出 2

1

当 k=1,展示活动可以按如下方式进行,例如:

  • 首先,佩戴新领带的模特出现在舞台上。最初,模特领带的长度是 1.
  • 第一场演出时,观众大喊 2。你忽略这一点。
  • 第二场演出时,观众大喊 1。您可以通过选择舞台上唯一的模特并将其领带长度设置为来回应这一点 1.
  • 第三场演出时,观众大喊 1。您可以通过选择舞台上唯一的模特并将其领带长度设置为来回应这一点 1.
  • 第四场演出时,观众大喊 2。您可以通过选择舞台上唯一的模特并将其领带长度设置为来回应这一点 2.
  • 第五场公演时,观众大喊 2。您可以通过选择舞台上唯一的模特并将其领带长度设置为来回应这一点 2.
  • 第六场演出时,观众大喊 1。你忽略这一点。

请注意,在上面的示例中,在第 2 次和第 3 次表演期间,领带长度已经是的模特 选择 1 ,领带长度设置为 再次 1 。 在领带长度不变的情况下,这种选择也是允许的。

因此,模型的最小数量 防止展示活动失败所需的 k 是 1,输出应该是 1.

此示例输入满足所有子任务的约束。

\换行


示例输入 3

10
2 4 6 7 4 5 5 3 4 1

示例输出 3

3

此示例输入满足子任务的约束 1,4,5,6, 和 7.