/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1100 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) があります。この整数列 A に対しては以下のような操作を行うことができます。
- A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, A_{l+1}\neq A_l を満たす l,r\ (1\leq l < r \leq N) を選ぶ。 A_{l+1},A_{l+2},\dots,A_{r-1} をすべて A_l で置き換える。この操作には r-l-1 のコストがかかる。
A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, A_{l+1}\neq A_l を満たすl,r\ (1\leq l < r \leq N) が存在しなくなるまで操作を行うとき、一連の操作にかかるコストの総和の最小値を求めてください。
制約
- 3 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
7 1 2 3 2 3 2 1
出力例 1
7
例えば (l,r)=(3,5), (2,6), (1,7) の順に操作を行うと A は (1,2,3,2,3,2,1)\rightarrow (1,2,3,3,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1) と変化し、上記のような l,r が存在しなくなります。このような一連の操作にかかるコストの総和は 1+3+5=9 です。
一方、 (l,r)=(2,4), (4,6), (1,7) の順に操作を行うと A は (1,2,3,2,3,2,1)\rightarrow (1,2,2,2,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1) と変化し、このような一連の操作にかかるコストの総和は 1+1+5=7 となります。
入力例 2
5 1 2 3 4 5
出力例 2
0
入力例 3
40 1 2 3 4 5 6 7 8 7 6 5 6 7 8 7 6 5 4 3 2 2 1 2 3 4 5 4 5 6 7 8 7 7 6 5 6 6 7 8 8
出力例 3
44
Score : 1100 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N. On this sequence, the following operation can be performed:
- Choose l and r (1\leq l < r \leq N) such that A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, and A_{l+1}\neq A_l. Replace each of A_{l+1},A_{l+2},\dots,A_{r-1} with A_l. The cost of this operation is r-l-1.
You will repeat this operation until there is no l and r (1\leq l < r \leq N) such that A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, and A_{l+1}\neq A_l. Find the minimum total cost of such a series of operations.
Constraints
- 3 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
7 1 2 3 2 3 2 1
Sample Output 1
7
For example, if you perform the operation with (l,r)=(3,5), (2,6), (1,7) in this order, A changes as follows: (1,2,3,2,3,2,1)\rightarrow (1,2,3,3,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1), after which there is no l and r with the said property. The total cost of this series of operations is 1+3+5=9.
On the other hand, if you perform the operation with (l,r)=(2,4), (4,6), (1,7) in this order, A changes as follows: (1,2,3,2,3,2,1)\rightarrow (1,2,2,2,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1). The total cost of this series of operations is 1+1+5=7.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
0
Sample Input 3
40 1 2 3 4 5 6 7 8 7 6 5 6 7 8 7 6 5 4 3 2 2 1 2 3 4 5 4 5 6 7 8 7 7 6 5 6 6 7 8 8
Sample Output 3
44