Фарбування камінців
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Перед вами стоять $$$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. ($$$32$$$ бали): кількість різних чисел серед всіх $$$a_i$$$ не більша за $$$2$$$;
2. ($$$33$$$ бали): $$$n\le 1\,000$$$;
3. ($$$35$$$ балів): без додаткових обмежень.

Приклад

Вхідні дані

    61 3 1 5 3 5

Вихідні дані

    3

Пояснення

У першому тесті камінці пофарбовані в кольори $$$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$$$).