/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
数列 s に対して、その数列を構成する数を 0 個以上取り除き、残った数を元の順番で並べて得られる数列を s の部分列と呼びます。 たとえば、(4, 2, 1) や (7, 4, 3, 2, 1) や (空列) は (7, 4, 3, 2, 1) の部分列ですが、(1, 2) は (7, 4, 3, 2, 1) の部分列ではありません。
長さ n の数列 s について、次の条件を満たす空でない数列 a, b, c が存在するとき、数列 s を五七五列であるといいます。
- 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) は五七五列ですが、(5, 5, 7) は五七五列ではありません。ex については a=(1), b=(2, 4), c=(3) の 3 つの数列が五七五列の条件を満たします。
項数 N の数列 x=(x_1, x_2, ..., x_N) が与えられます。各 x_i は 2 \leq x_i \leq 7 を満たします。 この数列 x から、五七五列である部分列を 1 つずつ取り除くとき、最大でいくつの五七五列を取り除けるか求めてください。
制約
- 1 \leq N \leq 100
- 2 \leq x_i \leq 7
- N, x_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 x_2 ... x_N
出力
取り除ける五七五列の最大個数を 1 行で出力せよ。
入力例1
5 2 3 5 4 3
出力例1
1
(2, 3, 5, 4, 3) は五七五列です。a=(1, 5), b=(2, 4), c=(3) の 3 つの数列が五七五列の条件を満たします。
入力例2
10 5 6 2 3 5 5 5 7 5 3
出力例2
2
まず、x の第 1, 3, 5, 6 項からなる (5, 2, 5, 5) の五七五列が取り除けます。 (5, 2, 5, 5) については、例えば a=(1), b=(2, 4), c=(3) の 3 つの数列が五七五列の条件を満たします。
x から第 1, 3, 5, 6 項を取り除いた残りの列は (6, 3, 5, 7, 5, 3) となります。 次に、残りの列の第 3, 4, 5 項からなる (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
Score : 200 points
Problem Statement
A subsequence is a sequence that can be derived from another sequence by deleting some (incuding 0) elements without changing the order of the remaining elements. For example, (4, 2, 1), (7, 4, 3, 2, 1), and (empty) are subsequences of (7, 4, 3, 2, 1), but (1, 2) is not.
A sequence s of length n is called "575-sequence" if there exist numerical sequences a, b, and c that satisfy the following constraints.
- A sequence made by concatenating a, b, and c is a permutation of (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
For example, ex=(ex_1, ex_2, ex_3, ex_4)=(5, 3, 5, 4) is a 575-sequence, but (5, 5, 7) is not. For ex, a=(1), b=(2, 4), and c=(3) satisfy the above constraints.
You are given a sequence x=(x_1, x_2, ..., x_N) of length N. Each term x_i satisfies 2 \leq x_i \leq 7. How many 575-sequences can you remove one by one from x?
Constraints
- 1 \leq N \leq 100
- 2 \leq x_i \leq 7
- N, x_i are integers
Input
Input is given from Standard Input in the following format:
N x_1 x_2 ... x_N
Output
Print the maximum number of 575-sequences you can remove from x.
Sample Input 1
5 2 3 5 4 3
Sample Output 1
1
(2, 3, 5, 4, 3) is a 575-sequence. a=(1, 5), b=(2, 4), and c=(3) satisfy the constraints of 575-sequence.
Sample Input 2
10 5 6 2 3 5 5 5 7 5 3
Sample Output 2
2
Firstly, you can remove a 575-sequence (5, 2, 5, 5), which consists of the first, third, fifth, and sixth terms of x. For (5, 2, 5, 5), for example, a=(1), b=(2, 4), and c=(3) satisfy the constraints.
The remaining sequence, where the first, third, fifth, and sixth terms are removed from x is (6, 3, 5, 7, 5, 3). You can remove a 575-sequence (5, 7, 5), which consists of the third, fourth, and fifth terms of the remaining sequence.
Sample Input 3
5 6 6 6 6 6
Sample Output 3
0
Sample Input 4
9 5 3 2 2 7 3 5 4 3
Sample Output 4
2
Sample Input 5
8 5 5 4 3 5 5 4 3
Sample Output 5
2
Sample Input 6
22 2 3 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 4 3 2
Sample Output 6
3