IT 지원실의 기간별 점검

문제

한 회사의 IT 지원실은 매일 업무를 마친 뒤 그날 처리를 완료한 지원 요청 수를 기록한다. 기록은 첫날부터 마지막 날까지 날짜 순서대로 보관되어 있다. 요청이 들어왔더라도 처리를 완료하지 못했다면 그날의 완료 건수에는 포함하지 않는다. 하루 동안 완료한 요청이 하나도 없을 수도 있으므로 기록값으로 0도 허용한다. 지원실은 보관된 기록을 바탕으로 여러 기간의 처리 현황을 확인하려고 한다. 하나의 조회에는 시작일 L과 종료일 R이 주어지며, L일과 R일을 모두 포함한 연속된 기간을 대상으로 한다. 각 조회에서 필요한 값은 두 가지이다. 첫 번째는 해당 기간의 완료 건수를 모두 더한 값이고, 두 번째는 해당 기간 중 완료 건수가 정확히 0인 날의 수이다. 두 번째 값은 미완료 요청의 수나 연속해서 쉬었던 기간의 길이를 뜻하지 않는다. 예를 들어 어떤 조회 기간의 기록이 차례로 2, 0, 3, 0이면 완료 건수의 합은 5이고 완료 건수가 0인 날은 2일이다. 완료 건수가 양수인 날은 그 값의 크기와 관계없이 두 번째 값에 포함하지 않는다. 기간 전체가 0으로 이루어져 있으면 첫 번째 값은 0이고 두 번째 값은 기간의 날짜 수와 같다. 모든 조회는 동일한 원본 기록을 기준으로 하며, 조회를 처리하는 도중에 날짜별 기록이 바뀌는 일은 없다. 조회 기간이 서로 겹치거나 완전히 같아도 각각 독립적으로 답한다. 시작일과 종료일이 같으면 그 하루만 확인한다. 날짜 번호는 1부터 시작하며, 기록이 없는 날짜를 포함하는 조회는 주어지지 않는다. 입력으로 주어진 순서대로 각 기간의 완료 건수 합과 완료 건수가 0인 날의 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록된 날짜 수 N과 조회 수 Q가 공백으로 구분되어 주어진다. 둘째 줄에 날짜별 완료 건수 A_1, A_2, …, A_N이 주어진다. 다음 Q개 줄에 조회의 시작일 L과 종료일 R이 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 10,000, 0 ≤ A_i ≤ 9, 1 ≤ L ≤ R ≤ N이다.

출력

각 조회에 대해 해당 기간의 완료 건수 합과 완료 건수가 0인 날의 수를 공백으로 구분하여 한 줄에 출력한다. 총 Q개 줄을 입력된 조회 순서대로 출력한다.

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

6 2
3 2
3 0
1 1

1 2
0
1 1
1 1

0 1
0 1

4 2
9 9 9 9
1 4
2 3

36 0
18 0

출처: Devin.KR 자체 제작