Фарбування камінців

Перед вами стоять $n$ камінців, кожен з яких пофарбований в колір, а саме $i$-ий камінець пофарбований в колір $a_i$.

За одну операцію ви можете вибрати будь-які два сусідні камінці та пофарбувати їх у будь-який однаковий колір.

Вам потрібно, щоб всі камінці стали однакового кольору за мінімальну кількість операцій.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 2\cdot 10^5)$ — кількість камінців.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$ — кольори камінців.

Вихідні дані

Виведіть єдине число — мінімальну кількість операцій.

Приклади

Примітка

У першому тесті камінці пофарбовані в кольори $1,3,1,5,3,5$ відповідно.

За першу операцію можна пофарбувати камінці на позиціях $4,5$ в колір $1$, після чого камінці будуть $1,3,1,1,1,5$.

Другою операцією можна пофарбувати камінці на позиціях $1,2$ в колір $1$. Тепер камінці пофарбовані в $1,1,1,1,1,5$.

Останньою операцією можна пофарбувати два останні камінці в колір $1$, після чого всі камінці будуть однакового кольору ($1$).

Оцінювання

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($32$ бали): кількість різних чисел серед всіх $a_i$ не більша за $2$;

2. ($33$ бали): $n\le 1000$;

3. ($35$ балів): без додаткових обмежень.