配点 : $600$ 点

問題文

$1$ 以上 $N$ 以下の整数のうち一つが書かれた $3N$ 枚のカードが左右一列に並んでいます。 左から $i$ 番目のカードに書かれた整数は $A_i$ です。

以下の操作を $N-1$ 回繰り返します。

• 左から $5$ 枚のカードを好きな順に並び替える。その後、左から $3$ 枚のカードを取り除く。このとき、その $3$ 枚のカードに書かれた整数がすべて等しければ $1$ 点を得る。

$N-1$ 回の操作の後、残った $3$ 枚のカードに書かれた整数がすべて等しければ追加で $1$ 点を得ます。

得られる得点の最大値を求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$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