15968번 - 물병 잡기 서브태스크

재혁이는 신기한 취미를 가지고 있다. 그 취미는 어떤 시간 T에 위치가 L 이상 R 이하인 모든 물병의 물을 맛보는 것이다!! 하지만, 가만히 앉아서 제자리에서 물만 먹던 재혁이는 비만에 걸릴 것을 우려하여 움직이기로 했다. 그리고 물병들은 자유분방하기 때문에 어떤 특정 상황이 되면 움직인다.

물병에는 1, 2, ..., N의 번호가 붙어 있고, i의 번호가 붙은 물병의 초기 위치는 -i이다. 재혁이의 초기 위치는 0이다. 재혁이와 물병들은 매초 순간이동을 하는데, 그 규칙은 다음과 같다.

1. 재혁이는 1초마다 오른쪽으로 1씩 움직인다.
2. 물병은 물이 쏟아질 것을 우려해서 함부로 움직이지 않는다. 재혁이가 이동한 후, 물병 1은 재혁이와의 거리가 D₁+1 이상 차이나면 (재혁이의 위치)-1로 이동한다.
3. 물병 1의 위치가 결정된 후, 물병 2는 물병 1과의 거리가 D₂+1 이상 차이나면 (물병 1의 위치)-1로 이동한다. 같은 방식으로 물병 3, 4, ..., N이 순서대로 이동한다. 즉 물병 i는 물병 i-1과의 거리가 D_i+1 이상 차이나면 (물병 i-1의 위치)-1로 이동한다.

재혁이는 무지막지하게 물을 먹다가 갑자기 어떤 시간 T와 구간 L, R에 대해서 자신이 몇개의 물을 마실 수 있는지 궁금해졌다. 그런데 물을 너무 많이 먹은 나머지 재혁이 자신도 물병이라고 착각하기 시작했다. 즉 재혁이의 위치가 L 이상 R 이하라면 질의의 답에 1을 더해야 한다. 재혁이를 위해 시간 T와 L, R들이 주어졌을 때 몇 개의 물병을 잡을 수 있는지 알려주자!

첫 번째 줄엔 물병의 개수 N(1 ≤ N ≤ 500,000)과 질의의 개수 Q(1 ≤ Q ≤ 500,000)가 주어진다.

다음 N개의 줄에 D_i(1 ≤ D_i ≤ 1,000,000,000)가 주어진다.

다음 Q개의 줄에 T_i, L_i, R_i(1 ≤ T_i, L_i ≤ 1,000,000,000, L_i ≤ R_i ≤ 1,000,000,000)가 주어진다.

Q줄에 걸쳐 질의의 답을 출력한다. 즉 i번째 줄에는 시간 T_i에 위치가 L_i 이상 R_i 이하인 물병이 몇 개인지 출력한다.

• D_i = 1

• 1 ≤ N,Q,T_i, L_i, R_i ≤ 1,000

• 위에서 주어진 제약조건 외 다른 조건 없음