/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
あなたは以下の操作を 0 回以上好きな順番で好きな回数行うことができます：
- A_k=A_{k+1}=A_{k+2}=A_{k+3} を満たす 1 以上 |A|-3 以下の整数 k を選び、A から A_k,A_{k+1},A_{k+2},A_{k+3} を削除する。（より厳密には、 A を (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N) に置き換える。）
ここで、 |A| は整数列 A の長さを表します。
操作を繰り返した後の最終的な |A| としてあり得る最小値を求めてください。
制約
- 1\le N\le 2\times 10^5
- 1\le A_i\le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
操作を繰り返した後の最終的な |A| としてあり得る最小値を出力せよ。
入力例 1
10 1 1 1 4 4 4 4 1 2 3
出力例 1
2
以下のように 2 回操作することで |A|=2 にすることができます。
- k=4 を選ぶ。A_4=A_5=A_6=A_7=4 が成り立つためこの選択は正当である。 A=(1,1,1,1,2,3) となる。
- k=1 を選ぶ。A_1=A_2=A_3=A_4=1 が成り立つためこの選択は正当である。 A=(2,3) となる。
|A| を 2 未満にすることはできないため、 2 を出力してください。
入力例 2
3 2 1 3
出力例 2
3
はじめから操作を行うことができません。
入力例 3
13 1 1 4 4 4 1 1 1 1 4 1 4 1
出力例 3
5
Score : 300 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
You can perform the following operation zero or more times in any order:
- Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)
Here, |A| represents the length of the integer sequence A.
Find the minimum possible value of the final |A| after repeating the operation.
Constraints
- 1\le N\le 2\times 10^5
- 1\le A_i\le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the minimum possible value of the final |A| after repeating the operation.
Sample Input 1
10 1 1 1 4 4 4 4 1 2 3
Sample Output 1
2
You can make |A|=2 with two operations as follows:
- Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
- Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.
It is impossible to make |A| less than 2, so output 2.
Sample Input 2
3 2 1 3
Sample Output 2
3
You cannot perform any operation from the beginning.
Sample Input 3
13 1 1 4 4 4 1 1 1 1 4 1 4 1
Sample Output 3
5