Как считать ответ на отрезке [i, j]?

Если a_i = a_j, то ответ: j - i + 1 (потому что числа упорядочены).

Иначе: ответ — максимум из:

• количества чисел, равных a[i], находящихся на позициях >= i (считается за O(1))
• количества чисел, равных a[j], находящихся на позициях <= j (считается за O(1))
• количества чисел, одновременно строго больших a[i] и строго меньших a[j] (считается, например, деревом отрезков за O(logN))

На всякий случай: кот, код.

На будущее: название записи должно быть, во-первых, информативным, во-вторых, не кричащим (бывают исключения). Я бы назвал Вашу запись как-то так: "E-Olymp 4081 (Частые значения — 2). Нужна помощь с решением."