AT_abc438_c [ABC438C] 1D puyopuyo

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

你可以执行以下操作零次或多次（任意顺序，任意次数）：

· 选择一个整数 $k$ 满足 $1 \leq k \leq |A|-3 且 A_k=A_{k+1}=A_{k+2}=A_{k+3}$，然后从 $A$ 中删除 $A_k,A_{k+1},A_{k+2},A_{k+3}$。（更准确地说，将 $A$ 替换为 $(A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N)$。）

这里，$|A|$ 表示整数序列 $A$ 的长度。

求重复进行操作后，最终 $|A|$ 可能的最小值。

输入格式

输入以以下格式从标准输入给出：

$N A_1 A_2 \ldots A_N$

输出格式

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

输入输出样例 #1

输入 #1

10
1 1 1 4 4 4 4 1 2 3

输出 #1

2

输入输出样例 #2

输入 #2

3
2 1 3

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

5

说明/提示

样例解释 1

可以通过以下两次操作使 $|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

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

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• 输入的所有值都是整数。