O(n^4) solution is accepted


#1

This solution is implemented using the array of cumulative sums.
O(n^3) also can be implemented.