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

你可以任意次、任意顺序地执行以下操作： 选择一个整数 $k$，满足 $1 \le k \le |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_1,A_2,\dots,A_{k-1},A_{k+4},A_{k+5},\dots,A_N)$ 替换 $A$。）

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

请你求出经过若干次操作后，最终 $|A|$ 的最小可能值。

约束条件

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

输入格式

输入从标准输入读取，格式如下：

N
A_1 A_2 … A_N

输出格式

输出经过若干次操作后，最终 $|A|$ 的最小可能值。

样例 1

Input

10
1 1 1 4 4 4 4 1 2 3

Output

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)$。 无法得到比 $2$ 更小的 $|A|$，所以输出 $2$。

样例 2

Input

3
2 1 3

Output

3

说明： 从一开始你就无法执行任何操作。

样例 3

Input

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

Output

5