D - Taking Sandwitches
Ceylon
2
s
1024
MB
400
点
問題文
長さ $N$ の数列 $A = (A_1, \cdots, A_N)$ が与えられます。
あなたはこの数列に対して以下の操作を好きな回数行うことができます。
- $A_l = A_r$ を満たす整数 $l,r \space(1 \leq l < r \leq |A|)$ を選び、数列から $A_l, A_{l+1}, \cdots ,A_r$ を削除する。その後、残った要素を元の順番で連結した数列を新たに $A$ とする。
操作の結果としてありえる数列 $A$ の長さの最小値を求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq A_i \leq N$
部分点
この問題には部分点が設定されています。
- $A_i \leq 2$ を満たすデータセットに正解した場合には、$200$ 点が与えられます。
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1 A_2 \cdots A_{N}$
出力
答えを 1 行に出力して下さい。
入力例 1
6
1 2 1 1 2 2
出力例 1
0
(最適ではない)操作の例として、$l=2, r=5$ を選んで操作を行うと、$A_2, A_3, A_4, A_5$ が削除され、操作後の $A$ は $(1,2)$ となります。
例えば $l=1, r=4$として操作を行うと $A = (2,2)$ となり、これに対し $l=1, r=2$ として操作を行うと $A$ の長さ $0$ を達成できるので、0 を出力します。
このケースは部分点の制約を満たします。
入力例 2
1
1
出力例 2
1
このケースでは $1$ 度も操作することができません。この場合、元の $A$ の長さである 1 を出力します。
このケースは部分点の制約を満たします。
入力例 3
12
1 2 3 2 4 3 1 4 5 1 2 5
出力例 3
1
例えば、$l=1, r=7$ として操作を行い $A = (4,5,1,2,5)$ としたあと、$l=2, r=5$ として操作を行うと $A= (4)$ となります。長さ $1$ より短くすることはできないので、1 を出力します。
このケースは部分点の制約を満たしません。
入力例 4
9
9 9 8 2 4 4 3 5 3
出力例 4
2
このケースは部分点の制約を満たしません。
入力例 5
5
1 2 3 4 5
出力例 5
5
このケースは部分点の制約を満たしません。