기상청이 \(N\)일 동안의 날씨를 기록했다. 각 날은 비가 온 날(1)이거나 오지 않은 날(0)이다. \(Q\)개의 질문이 주어지는데, 각 질문은 두 정수 \(l\), \(r\)로 이루어져 있으며 \(l\)일째부터 \(r\)일째까지 비가 온 날이 며칠인지 묻는다.

각 질문에 대한 답을 출력하여라.

• \(1 \le N \le 100\,000\)
• \(1 \le Q \le 100\,000\)
• 각 값은 \(0\) 또는 \(1\)
• \(1 \le l \le r \le N\)

첫째 줄에 날의 수 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.

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

다음 \(Q\)개의 줄에 각각 두 정수 \(l\), \(r\) \((1 \le l \le r \le N)\) 이 주어진다.

각 질문에 대해 비가 온 날의 수를 한 줄에 하나씩, 질문 순서대로 출력한다.

riseoj 작성

출처 Original