Brave CHAIN

题目描述

我们有从左到右排列的 $3N$ 张卡片，每张卡片上写着一个在 $1$ 到 $N$（含）之间的整数。第 $i$ 张（从左数）卡片上写的整数是 $A_i$。 你将进行以下操作 $N-1$ 次：

任意重排最左边的五张卡片的顺序，然后移除最左边的三张卡片。如果被移除的这三张卡片上写的整数都相同，则你得 $1$ 分。

在这 $N-1$ 次操作之后，如果剩下的三张卡片上写的整数都相同，你将再额外得到 $1$ 分。 求你最多可以得到多少分。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\cdots$ $A_{3N}$

输出格式

输出你最多可以得到的分数。

2
1 2 1 2 2 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$我们把最左边的五张卡片重排，使得六张卡片从左到右写着 $2\ 2\ 2\ 1\ 1\ 1$。 然后，移除最左边的三张卡片，这三张卡片上写的都是相同的整数 $2$，因此得到 $1$ 分。 现在，剩下的卡片上写着 $1\ 1\ 1$。 由于这三张卡片上的整数都是相同的 $1$，我们再得到 $1$ 分。 这样我们可以得到 $2$ 分——这是可能的最大值。

标签: AtCoder|abc176F

来源

AtCoder|abc176F