P Insert and Concatenate

制限時間: 2 sec メモリ制限: 1024 MB

Insert and Concatenate

Statement

正の整数からなる列 \(S,T\) があります。最初、\(S\) と \(T\) はいずれも空の数列です。以下の操作を何回でも行えます。

\(S\) の任意の位置に任意の正の整数を挿入する。この操作には \(1\) のコストがかかる。
\(T\) の後ろに \(S\) を連結させる。この操作にはコストがかからない。

\(1\) 以上 \(N\) 以下の整数からなる、長さ \(N\) の数列 \(A=(A_1,A_2,\dots,A_N)\) が与えられます。\(A\) が \(T\) の連続する部分列になる (すなわち、ある正の整数 \(i,j\) が存在して、\(T\) の \(i\) 番目の要素から \(j\) 番目の要素を取り出したものが \(A\) と一致する) ようにするために必要な総コストの最小値を求めてください。

Input

入力は以下の形式で標準入力から与えられます。

	\(N\)
	\(A_1~A_2~\dots~A_N\)

入力は以下の制約をすべて満たします。

\(1 \leq N \leq 2 \times 10^5\)
\(1 \leq A_i \leq N~(1\leq i\leq N)\)
入力はすべて整数

Output

答えを \(1\) 行に出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

(10 点): \(A_i=\mathrm{max}(i-10,1)\)
(15 点): \(A\) の要素として同じ数はたかだか \(2\) 回しか現れない。
(20 点): \(N\leq 500\)
(55 点): 追加の制約はない。

Examples

Input 1

5
2 3 1 2 3

Output 1

Input 2

12
1 1 1 1 1 1 1 1 1 1 1 2

Output 2

Note

1つ目のテストケースについて、例えば以下の順に操作することでコスト \(3\) で \(T=(1,2,3,1,2,3)\) にすることができ、これが最適です。

\(S\) の末尾に \(1\) を挿入する。\(S=(1),T=()\)
\(S\) の末尾に \(3\) を挿入する。\(S=(1,3),T=()\)
\(S\) の \(2\) 番目に \(2\) を挿入する。\(S=(1,2,3),T=()\)
\(T\) の後ろに \(S\) を連結させる。 \(S=(1,2,3),T=(1,2,3)\)
\(T\) の後ろに \(S\) を連結させる。 \(S=(1,2,3),T=(1,2,3,1,2,3)\)

1つ目のテストケースは2番目と3番目の部分点制約を、2つ目のテストケースは1番目と3番目の部分点制約を満たします。

サンプル