물병 잡기

재혁이는 특이한 취미가 있다. 그 취미는 시간 $T$에 위치가 $L$ 이상 $R$ 이하인 모든 물병의 물을 맛보는 것이다. 하지만 제자리에 가만히 앉아 물만 마시던 재혁이는 비만이 걱정되어 움직이기로 했다. 물병들은 자유분방해서 특정 상황이 되면 움직인다.

물병에는 $1, 2, \ldots, N$번 번호가 붙어 있고, 번호 $i$인 물병의 초기 위치는 $-i$이다. 재혁이의 초기 위치는 $0$이다. 재혁이와 물병들은 매초 다음 규칙에 따라 움직인다.

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

재혁이는 물을 무지막지하게 마시다가, 시간 $T$와 구간 $L$, $R$이 주어졌을 때 자신이 몇 개의 물병을 잡을 수 있는지 궁금해졌다. 그런데 물을 너무 많이 마신 나머지 재혁이 자신도 물병이라고 착각하기 시작했다. 그러므로 재혁이의 위치가 $L$ 이상 $R$ 이하이면 질의의 답에 1을 더해야 한다.

첫 번째 줄에 물병의 개수 $N$ ($1 \le N \le 500{,}000$)과 질의의 개수 $Q$ ($1 \le Q \le 500{,}000$)가 주어진다. 다음 $N$개의 줄에 $D_i$ ($1 \le D_i \le 10^9$)가 주어진다. 다음 $Q$개의 줄에 $T_i$, $L_i$, $R_i$ ($1 \le T_i, L_i \le 10^9$, $L_i \le R_i \le 10^9$)가 주어진다.

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