 # Editorial-MINIMIZESIN

First, let’s solve the problem with a fixed array A. Let’s calculate the array of prefix sums P_i = A_1+\ldots+A_i. We have: | \sin (A_X+A_{X+1}+\dots+A_Y) |=|\sin(P_Y-P_{X-1})|=\sin(|P_Y-P_{X-1}| \mod 180). So, on the segment [X-1, Y] you need to find two prefix sums as close as possible modulo 180. With one pass through the array P, looping from X-1 to Y, you can mark in an additional array of length 180 which prefix sums are found, and then go through this array and update the answer with all neighboring pairs. The complexity of this algorithm is O(N + 180).

But you can see that if we find two identical prefix sums in the cycle from X-1 to Y, we can immediately return the answer: then we have found such X, Y that | \sin (A_X+A_{X+1}+\dots+A_Y)|=0. So, in this implementation, this loop will run at most 180 iterations — otherwise, according to the Dirichlet principle, there will be two prefix sums that are identical by 180 modulo.

The last thing to note is that it is not necessary to calculate prefix sums in advance. You can calculate them in the same loop. Thus, no additional structures are required at all, and you can update the array elements simply by saving them. The complexity of this solution is O(N + 180\cdot Q).