관측 기록의 빗물 합계

문제

산기슭의 날씨 관측소는 일정한 시간 간격으로 빗물 수집통에 새로 모인 물의 양을 기록한다. 기록을 한 번 마치면 수집통을 비우므로, 각 기록의 값은 바로 앞 기록 이후에 새로 모인 양만 나타낸다. 관측소는 하루 동안 얻은 기록을 시간순으로 보관하고 각 기록에 1번부터 N번까지 번호를 붙였다. 관측소의 연구원은 여러 시간 구간의 강수량을 비교하려 한다. 연구원이 요청하는 구간은 첫 기록 번호 L과 마지막 기록 번호 R로 주어진다. 이 요청의 답은 L번 기록부터 R번 기록까지 적힌 값을 모두 더한 것이다. 양 끝 번호의 기록도 합계에 포함한다. L과 R이 같으면 해당 기록 하나의 값이 답이며, 구간에 속한 모든 기록이 0이면 답도 0이다. 기록에 적힌 값은 관측소에서 정한 정수 단위로 표시한다. 값이 0이라는 것은 그 관측 간격 동안 새로 모인 빗물이 없었다는 뜻이다. 구간의 길이로 나눈 평균이나 서로 다른 시각의 값의 차이를 구하는 것이 아니며, 주어진 정수들을 그대로 더하면 된다. 기록 번호는 실제 시각 대신 사용하므로 시각을 다른 단위로 바꾸는 작업도 필요하지 않다. 모든 요청은 같은 관측 기록을 대상으로 한다. 요청을 처리하는 동안 기록이 수정되거나 삭제되는 일은 없다. 여러 요청의 구간은 서로 겹칠 수 있고, 같은 구간이 여러 번 요청될 수도 있다. 이 경우에도 각 요청에 대한 답을 별도로 출력해야 한다. 먼저 주어진 요청부터 차례로 답하며, 합계가 같은 요청 사이에 별도의 우선순위는 없다. 관측 기록과 연구원의 요청 목록이 주어질 때, 각 구간에 새로 모인 빗물의 총량을 구한다.

입력

첫째 줄에 기록의 개수 N과 요청의 개수 Q가 공백으로 구분되어 주어진다. N과 Q는 정수이며 1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 10,000이다.
둘째 줄에 각 기록의 빗물 양 a₁, a₂, …, aₙ이 시간순으로 공백으로 구분되어 주어진다. 각 aᵢ는 0 이상 9 이하의 정수이다.
다음 Q개 줄에는 요청의 두 정수 L, R이 공백으로 구분되어 주어진다. 각 요청은 1 ≤ L ≤ R ≤ N을 만족한다.

출력

각 요청에 대해 L번부터 R번까지 기록된 빗물 양의 합을 정수 하나로 출력한다. 요청이 주어진 순서대로 총 Q개 줄을 출력한다.

7 4
2 0 5 1 0 3 4
1 3
4 7
2 2
1 7

7
8
0
15

1 3
9
1 1
1 1
1 1

9
9
9

4 2
0 0 0 0
1 4
2 3

0
0

출처: Devin.KR 자체 제작