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

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

1 секунда

256 мегабайтів

Середня

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад

Примітка

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

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

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

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

Оцінювання

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

( $32$ бали): кількість різних чисел серед всіх $a_{i}$ a_i не більша за $2$ ;
( $33$ бали): $n \leq 1000$ n\le 1\,000;
( $35$ балів): без додаткових обмежень.