숫자 N개가 한 줄로 놓여 있어요. L번째부터 R번째까지의 합을 묻는 질문이 Q개 들어와요. 각 질문에 빠르게 답해 보세요.
힌트: 질문마다 처음부터 더하면 느려요. 앞에서부터의 누적 합을 미리 만들어 두면 어떨까요?
입력
첫째 줄에 수의 개수 N이 주어져요. (1 ≤ N ≤ 10,000) 둘째 줄에 N개의 정수가 공백으로 구분되어 주어져요. (-1,000 ≤ 수 ≤ 1,000) 셋째 줄에 질문 수 Q가 주어져요. (1 ≤ Q ≤ 6,000) 다음 Q개의 줄에 L과 R이 주어져요. (1 ≤ L ≤ R ≤ N)
출력
각 질문에 대해 L번째부터 R번째까지의 합을 한 줄에 하나씩 출력해요.