Problem Description

There is an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $ N $. For this sequence $ A $, the following operation can be performed:

• Choose $l,r\ (1\leq\ l\ <\ r\ \leq\ N)$ such that $A_l=A_r,\ A_{l+1}=A_{l+2}=\dots=A_{r-1},\ A_{l+1}\neq\ A_l$. Replace $A_{l+1},A_{l+2},\dots,A_{r-1}$ with $ A_l $. This operation costs $ r-l-1 $.

Continue performing operations until there are no more $l,r\ (1\leq\ l\ <\ r\ \leq\ N)$ that satisfy $A_l=A_r,\ A_{l+1}=A_{l+2}=\dots=A_{r-1},\ A_{l+1}\neq\ A_l$. Find the minimum total cost of all operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $\dots$ $ A_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

7
1 2 3 2 3 2 1

Sample Output #1

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

Notes/Hints

Constraints

• $3\ \leq\ N\ \leq\ 5\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ N$
• All values input are integers

Sample Explanation 1

For example, if operations are performed in the order $(l,r)=(3,5),\ (2,6),\ (1,7)$, $ 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)$, and no more $ l,r $ exist. The total cost of such a series of operations is $ 1+3+5=9 $. On the other hand, if operations are performed in the order $(l,r)=(2,4),\ (4,6),\ (1,7)$, $ 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)$, and the total cost of such a series of operations is $ 1+1+5=7 $.

见题面 Input 部分

见题面 Output 部分