Рассмотрим все вхождения числа $$$x$$$ в наш массив $$$i_1, i_2, i_3, \ldots, i_k$$$. При индексе разреза от $$$i_1$$$ до $$$i_2$$$ или от $$$i_{k-1}$$$ до $$$i_k$$$ к ответу добавится 1 (так как с одной стороны от разреза будет одно вхождение числа $$$x$$$, а с другой $$$k - 1$$$). При индексе разреза от $$$i_2$$$ до $$$i_3$$$ или от $$$i_{k-2}$$$ до $$$i_{k-1}$$$ добавится $$$2$$$. И так далее. Получается что-то похожее на арифметическую прогрессию, которая сначала возрастает, а потом убывает.

Давайте считать ответы для отрезков в алгоритме МО. Будем поддерживать для каждого индекса сумму вкладов по всем числам, которую принесёт разрез по этому индексу. Тогда ответ на отрезке — максимум на отрезке.

Если мы добавляем новое число справа к нашему отрезку, то мы хотим пересчитать вклад только этого нового числа (вклады остальных чисел останутся такими же). Для этого достаточно добавить единицу на правой половине наших вхождений числа (из рассуждений первого абзаца).

Аналогично можно обрабатывать добавления/удаления чисел справа/слева нашего отрезка.

Для прибавления на отрезке и взятия максимума можно использовать ДО на массовых операциях. (Для ускорения нужно хранить разностный массив нашего списка. Тогда будет прибавление в точке и нахождение максимальной суммы на отрезке, это можно реализовать ДО без массовых операций либо ДО снизу.)

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

Итого асимптотика $$$O(n \sqrt{n} \log n))$$$. Здесь важно писать так, чтобы константа была как можно меньше.