\begin{tutorial}{Робин Гуд и массив}

Пусть мы выполнили одну операцию. После выполнения этой операции массив будет иметь вид $a_1, \ldots, a_{i - 2}, x, x, x, a_{i + 2}, \ldots, a_n$, где $x = \operatorname{median}(a_{i - 1}, a_i, a_{i + 1})$. Заметим, что теперь мы можем сделать все элементы массива равными $x$. Для этого надо применить операцию к элементам, которые стоят на позициях $i - 2, i - 1, i$, чтобы элемент на позиции $i - 2$ тоже стал равен $x$. Таким образом мы сможем расширить влево и вправо отрезок массива, который состоит из элементов равных $x$, до тех пор пока он не займет весь массив.

Заметим, что если мы хотим приравнять все элементы массива к какому-то числу $y$, то мы должны уметь получать подмассив $y, y, y$ первой операцией. Если это не так, то не существует элементов, равных $y$, на расстоянии хотя бы два. Такие элементы не появятся после применения любых операций, а потому количество элементов равных $y$ будет только уменьшаться.

Из вышеописанного факта следует, что мы можем перебрать $a_{i - 1}, a_i, a_{i + 1}$ и взять в качестве ответа \textbf{максимум} по $\operatorname{median}(a_{i - 1}, a_i, a_{i + 1})$.

Асимптотика решения $\mathcal{O}(n)$.


\end{tutorial}
