拼图

题目描述

有 $3N$ 张卡片,每张卡片上写着 $1$ 以上 $N$ 以下的一个整数,它们从左到右排成一列。 左起第 $i$ 张卡片上写的整数是 $A_i$。

重复以下操作 $N-1$ 次:

• 将左起 $5$ 张卡片按任意顺序重新排列。然后,取走左起 $3$ 张卡片。此时,如果这 $3$ 张卡片上写的整数全部相等,则获得 $1$ 分。

在 $N-1$ 次操作后,如果剩下的 $3$ 张卡片上写的整数全部相等,则额外获得 $1$ 分。

求能获得的最大得分。

输入格式

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

$N$
$A_1$ $A_2$ $\cdots$ $A_{3N}$

输出格式

输出能获得的最大得分。

样例

2
1 2 1 2 2 1

2

重新排列左起 $5$ 张卡片,使卡片上写的整数从左到右为 $2\ 2\ 2\ 1\ 1\ 1$。

取走左起 $3$ 张卡片,此时这 $3$ 张卡片上写的整数全部是 $2$,相等,因此获得 $1$ 分。

卡片上写的整数从左到右变为 $1\ 1\ 1$。

剩下的 $3$ 张卡片上写的整数全部是 $1$,也相等,因此获得 $1$ 分。

总得分为 $2$,这是最高分。

3
1 1 2 2 3 3 3 2 1

1

3
1 1 2 2 2 3 3 3 1

3

数据范围

• $1 \leq N \leq 2000$
• $1 \leq A_i \leq N$