← 返回题目列表

AtCoder · kupc2017_f

F. 五百七十五

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

分数: 200 点

问题陈述

子序列是可以通过删除某些序列(包括 0) 元素而不改变其余元素的顺序。例如, (4, 2, 1), (7, 4, 3, 2, 1),和 (empty) 是子序列 (7, 4, 3, 2, 1),但是 (1, 2) 不是。 如果存在数字序列,则

一个序列 s 长度 n 称为“575-序列” a, b,和 c 满足以下约束。

  • 通过连接形成的序列 a, b,和 c 是一个排列 (1, 2, ..., n).
  • min_i(a_i) < min_i(b_i) < min_i(c_i)
  • Σs_{a_i} = 5
  • Σs_{b_i} = 7
  • Σs_{c_i} = 5

例如, ex=(ex_1, ex_2, ex_3, ex_4)=(5, 3, 5, 4) 是一个 575 序列,但是 (5, 5, 7) 不是。 ex, a=(1), b=(2, 4),和 c=(3) 满足上述约束。

给你一个序列 x=(x_1, x_2, ..., x_N) 长度 N.每学期 x_i 满足 2 \leq x_i \leq 7。 你能一一删除多少个575序列 x?

约束

  • 1 \leq N \leq 100
  • 2 \leq x_i \leq 7
  • N, x_i 是整数

输入

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

N
x_1 x_2 ... x_N

输出

打印可以从中删除的 575 序列的最大数量 x.


示例输入 1

5
2 3 5 4 3

示例输出 1

1

(2, 3, 5, 4, 3) 是一个 575 序列。 a=(1, 5), b=(2, 4),和 c=(3) 满足575序列的约束。


示例输入 2

10
5 6 2 3 5 5 5 7 5 3

示例输出 2

2

首先,您可以删除575序列 (5, 2, 5, 5),由第一、第三、第五和第六项组成 x。 对于 (5, 2, 5, 5),例如, a=(1), b=(2, 4),和 c=(3) 满足约束条件。

剩余序列,其中第一项、第三项、第五项和第六项已从 x is (6, 3, 5, 7, 5, 3)。 您可以删除 575 序列 (5, 7, 5),由剩余序列的第三、第四和第五项组成。


示例输入 3

5
6 6 6 6 6

示例输出 3

0

示例输入 4

9
5 3 2 2 7 3 5 4 3

示例输出 4

2

示例输入 5

8
5 5 4 3 5 5 4 3

示例输出 5

2

示例输入 6

22
2 3 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 4 3 2

示例输出 6 有

3