← 返回题目列表

AtCoder · abc176_f

F. 勇敢链

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有 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