AT_arc181_f [ARC181F] Colorful Reversi

[problemUrl]: https://atcoder.jp/contests/arc181/tasks/arc181_f 長さ $ 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\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。

### 制約 - $ 3\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ - 入力される値はすべて整数 ### Sample Explanation 1 例えば $ (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 $ となります。