## Editorial for Marathon

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Do you know how to implement a prefix sum array? Halfway through making this question, we realized this is almost identical to a past DMOPC problem called Deforestation. So, if you finished that problem, you should've been able to do this as well. The naive solution would be to sum up the ratings between episode and episode and subtract that from the total rating each time. This unfortunately takes time per query, and total, which will not pass all the test cases.

To get full marks, we need a way to solve queries in time. This is where the intuitive-ity of the prefix sum array comes to play. The th element of our prefix sum array will hold the sum of all ratings from episodes to episode . This prefix sum array can be computed in time. Now, how do we use this array to our advantage? The sum between two integers () is just ! Why is this? holds . psum[a-1] holds . Therefore, if you take , you will be left with . You should do a few cases by hand, to understand it better. Once you get the range sum, subtract it from the total rating to get the answer to your query. Since you only need 2 operations per query, the time complexity is , and your total complexity has been reduced to . Despite the difficult concept, the code is quite simple.

import sys
raw_input = sys.stdin.readline ## DONT FORGET THIS PYTHON IS SUPER SLOW
n,q = map(int,raw_input().split())
prefixsum = [0]+map(int,raw_input().split())
for i in xrange(1,n+1):
prefixsum[i] += prefixsum[i-1]
tot = prefixsum[-1]
for i in xrange(q):
a,b = map(int,raw_input().split())
print tot - prefixsum[b] + prefixsum[a-1]