10118 출석 누적 조회 Silver III

문제

학생 A는 매일 출석 체크를 한다. 첫째 날부터 N째 날까지의 출석 기록이 0(결석)과 1(출석)로 주어진다. 관리자가 총 M개의 기간 쿼리를 요청하는데, 각 쿼리는 두 정수 L, R로 주어지며 L일차부터 R일차까지 출석한 날의 수를 즉시 알려주어야 한다.

입력

첫째 줄에 N (1 ≤ N ≤ 200,000)과 M (1 ≤ M ≤ 200,000)이 주어진다.

둘째 줄에 N개의 정수(0 또는 1)가 공백으로 구분되어 주어진다.

다음 M개의 줄에 각 쿼리의 L, R이 주어진다. (1 ≤ L ≤ R ≤ N)

출력

각 쿼리에 대해 L일차부터 R일차까지 출석한 날의 수를 한 줄에 하나씩 출력한다.