Greedy solution is too slow because of the limits.

Can you solve this problem offline by doing some pre-processing?

Calculate the answers for all indexes moving to their left and to their right.