分数: 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