Пусть мы выполнили одну операцию. После выполнения этой операции массив будет иметь вид $$$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}$$$ и взять в качестве ответа максимум по $$$\operatorname{median}(a_{i - 1}, a_i, a_{i + 1})$$$.

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