이건 꼭 풀어야 해!

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 $N$짜리 수열 $A$를 만들고, $A$를 비내림차순으로 정렬해서 수열 $B$를 만들어 버렸다!! 여기서 $B$를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 $Q$개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

• L R: $B_L + B_{L+1} + \cdots + B_{R-1} + B_R$ 을 출력한다.

Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정

욱제의 질문에 답하고 함께 엠티를 떠나자!!

첫 번째 줄에 수열 $A$의 길이 $N$과 질문의 개수 $Q$가 공백으로 구분되어 주어진다. (1 ≤ $N$, $Q$ ≤ 300,000)

두 번째 줄에 $N$개의 정수 $A_1$, $A_2$, ..., $A_N$ 이 공백으로 구분되어 주어진다. $A_i$ 는 수열 $A$의 $i$ 번째 수이다. (1 ≤ $A_i$ ≤ 1,000)

세 번째 줄부터 $Q$개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 $L$, $R$이 공백으로 구분되어 주어진다. (1 ≤ $L$ ≤ $R$ ≤ $N$)

주어지는 모든 입력은 자연수이다.

$Q$개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

비내림차순은 원소가 감소하지 않는 (같거나 증가하는) 순서를 말한다.

while (Q--) { int sum = 0, L, R; scanf(“%d %d”, &L, &R); for (int i = L; i <= R; i++) { sum += a[i]; } printf(“%d\n”, sum); }

위와 같이 각 질문마다 반복문을 매번 돌려서 답을 계산하면, 시간복잡도가 $O(QN)$이 되므로 시간 초과를 받게 된다. 다른 방법을 이용해 문제를 해결해야 한다.