Hi Codeforces, Can you solve this problem?

Consider oranges as +1 and apples as -1.

Do the partial sum on the array. Now we want to find for every i , the maximum j such that for each i <  = k <  = j, partial[k] >  = partial[i] .

You can find such j using binary search and RMQ. (This is possible with simple stack too in O(n) ).

For all i (1 <= i <= n) calc the largest p[i] such that for all i <= k <= p[i] count of 'p' in a[i:k] > count of 'j' in a[i:k] it can be done using prefixes and binary search

Similarly, calc s (for all (1 <= i <= n) lowest s[i] such adding fruits from i to s[i] is possible)

Make tree segment on s. Bruteforce left part of line. To find answer which starts in left you need to find the largest t such s[t] <= left for i <= t <= p[left], t can be finded by down search in tree segment