← 返回题目列表

AtCoder · abc438_c

E. 1D 噗哟噗哟

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

分数: 300 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.

您可以按任意顺序执行以下操作零次或多次:

  • 选择一个整数 k 之间 1 和 |A|-3,包含在内,这样 A_k=A_{k+1}=A_{k+2}=A_{k+3},并删除 A_k,A_{k+1},A_{k+2},A_{k+3} 来自 A。 (更正式地说,替换 A 与 (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)

在这里, |A| 表示整数序列的长度 A.

找到最终的最小可能值 |A| 重复操作后。

约束

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

输出最终的最小可能值 |A| 重复操作后。


示例输入 1

10
1 1 1 4 4 4 4 1 2 3

示例输出 1

2

你可以 |A|=2 有两个操作如下:

  • 选择 k=4。此选择有效,因为 获得 A_4=A_5=A_6=A_7=4 成立。 A=(1,1,1,1,2,3) 。
  • 选择 k=1。此选择有效,因为 获得 A_1=A_2=A_3=A_4=1 成立。 A=(2,3) 。

不可能使 |A| 小于 2,所以输出 2.


示例输入 2

3
2 1 3

示例输出 2

3

您无法从一开始就执行任何操作。


示例输入 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

示例输出 3

5