\begin{center}
\begin{tabular}{rl}
\textbf{Автор задачі}: & \textbf{Олександр Тимкович} \\
\textbf{Задачу підготував}: & \textbf{Олександр Тимкович} \\
\textbf{Розбір написав}: & \textbf{Олександр Тимкович} 
\end{tabular} 
\end{center}
\textbf{Рішення для} $n\le 1\,000$:

Давайте перебирати колір, в який будуть пофарбовані всі камінці в кінці. Щоб знайти мінімальну кількість пофарбувань для певного кольору можна слідувати такому жадібному алгоритму:
\begin{itemize}
\item якщо колір камінця який ми перебираємо то йдемо далі;
\item інакше, фарбуємо теперішній на наступний камінці в колір який перебираємо.
\end{itemize}

\textbf{повне рішення}:

Припустимо ми перебираємо колір $C$. За яку мінімальну кількість операцій можна пофарбувати відрізок $[l,r]$ де крайні камінці кольору $C$, та інших камінців крім крайніх кольору $C$ нема? З алгоритму до рішення $n\le 1000$ випливає відповідь $\lfloor \frac{r-l}{2} \rfloor$.

Можемо розбити масив на такі відрізки, та загальна відповідь для кольору $C$ це сума відповідей на кожному відрізку. (Також потрібно не забути що можливо треба пофарбувати префікс і суфікс).

Отже рішення, це обчислювати кожен колір окремо. Для кольору $C$ ми навели алгоритм з складністю $O(occ(C))$ де $occ(C)$ це кількість входжень числа $C$ в масив. Сумарно для всіх кольорів рішення з складністю $O(n)$.

\newpage