순환선의 안내판 묶음

문제

한 지하철 순환선에는 N개의 역이 있다. 역에는 운행 방향을 따라 1번부터 N번까지 번호가 붙어 있다. 열차는 1번 역에서 2번 역으로 이동하는 방향으로 운행하며, N번 역 다음에는 다시 1번 역에 도착한다. 각 역에는 교체해야 할 안내판이 정해진 개수만큼 쌓여 있다. 안내판이 하나도 없는 역도 있다. 시설 담당자는 여러 가지 작업 구간을 검토하고 있다. 작업 구간 하나는 시작 역 s와 마지막 역 t로 정한다. 이 구간을 맡은 작업자는 s번 역에서 출발하여 운행 방향으로 이동하면서 방문한 역의 안내판을 모두 교체하고, t번 역의 작업을 마치면 즉시 멈춘다. 시작 역과 마지막 역의 안내판도 모두 작업량에 포함된다. s가 t보다 작으면 번호가 s 이상 t 이하인 역들을 차례대로 방문한다. s가 t보다 크면 s번 역부터 N번 역까지 방문한 다음, 1번 역으로 넘어가 t번 역까지 방문한다. s와 t가 같으면 그 역 하나만 방문한다. 이 경우 순환선을 한 바퀴 도는 것으로 해석하지 않는다. 따라서 어떤 작업 구간에서도 같은 역을 두 번 방문하지 않는다. 각 검토는 처음 주어진 안내판 개수를 기준으로 독립적으로 이루어진다. 앞에서 검토한 구간에 포함되었다고 해서 안내판이 없어지거나 다른 역으로 옮겨지지는 않는다. 같은 작업 구간이 여러 번 주어질 수도 있으며, 그때마다 해당 구간의 작업량을 출력해야 한다. 담당자는 구간별 작업량을 비교하려고 하지만, 가장 작은 구간이나 가장 큰 구간을 고를 필요는 없다. 각 구간에서 교체할 안내판의 총개수만 입력된 순서대로 구하면 된다. 모든 역의 안내판 개수와 Q개의 작업 구간이 주어졌을 때, 각 구간의 총개수를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 역의 수 N과 작업 구간의 수 Q가 주어진다. N과 Q는 각각 1 이상 10,000 이하인 정수다.
둘째 줄에 각 역의 안내판 개수 A1, A2, ..., AN이 주어진다. Ai는 0 이상 10,000 이하인 정수다.
다음 Q개 줄에 시작 역 s와 마지막 역 t가 주어진다. s와 t는 각각 1 이상 N 이하인 정수다.

출력

각 작업 구간에서 교체할 안내판의 총개수를 정수 하나로 출력한다. 출력은 구간이 입력된 순서대로 한 줄에 하나씩 한다. 해당 구간에 안내판이 없으면 0을 출력한다.

5 4
3 0 4 2 6
2 4
4 2
3 3
1 5

6
11
4
15

1 2
0
1 1
1 1

0
0

출처: Devin.KR 자체 제작