题目描述

我们有 $3N$ 张卡片按从左到右排列，每张卡片上写有从 $1$ 到 $N$（包括边界值）的整数。第 $i$ 张卡片上写的整数是 $A_i$。

你将进行以下操作 $N-1$ 次：

• 将最左边的五张卡片任意排序，然后移除最左边的三张卡片。如果这三张卡片上的整数都相等，你会得到 $1$ 分。

在进行了这 $N-1$ 次操作之后，如果剩下的三张卡片上的整数都相等，你将再得到 $1$ 分。

找出你能获得的最大分数。

约束条件

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

输入

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

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

输出

输出你能获得的最大分数。

示例输入 1

2
1 2 1 2 2 1

示例输出 1

2

我们重新排列最左边的五张卡片，使得六张卡片上写的整数从左到右依次为 $2\ 2\ 2\ 1\ 1\ 1$。

然后，移除最左边的三张卡片，这三张卡片上的整数都是 $2$，得到 $1$ 分。

现在，剩下的卡片上写的整数是 $1\ 1\ 1$。

因为这三张卡片上的整数都是 $1$，我们再得到 $1$ 分。

通过这种方式，我们可以得到 $2$ 分 - 这是最大可能的分数。

示例输入 2

3
1 1 2 2 3 3 3 2 1

示例输出 2

1

示例输入 3

3
1 1 2 2 2 3 3 3 1

示例输出 3

3