Catching Water Bottles

Jaehyeok has an unusual hobby. At time $T$, he tastes the water of every bottle whose position is between $L$ and $R$, inclusive. But he had been sitting still and drinking water in place, and he worried about becoming obese, so he decided to move. The bottles are free-spirited and move when a certain condition holds.

The bottles are numbered $1, 2, \ldots, N$, and the initial position of bottle $i$ is $-i$. Jaehyeok starts at $0$. Every second, Jaehyeok and the bottles move according to these rules.

1. Jaehyeok moves $1$ to the right every second.
2. Bottles do not move carelessly, since the water might spill. After Jaehyeok moves, bottle $1$ moves to (Jaehyeok's position) $-1$ if its distance from Jaehyeok is at least $D_1+1$.
3. After bottle $1$'s position is decided, bottle $2$ moves to (bottle $1$'s position) $-1$ if its distance from bottle $1$ is at least $D_2+1$. Bottles $3, 4, \ldots, N$ move in the same way, in order. That is, bottle $i$ moves to (bottle $i-1$'s position) $-1$ if its distance from bottle $i-1$ is at least $D_i+1$.

Jaehyeok drank so much water that he began to wonder how many bottles he can catch, given $T$, $L$, and $R$. He had also started to think he was a bottle himself. So if Jaehyeok's position is between $L$ and $R$ inclusive, add $1$ to the answer.

The first line contains the number of bottles $N$ ($1 \le N \le 500{,}000$) and the number of queries $Q$ ($1 \le Q \le 500{,}000$). The next $N$ lines each contain $D_i$ ($1 \le D_i \le 10^9$). The next $Q$ lines each contain $T_i$, $L_i$, and $R_i$ ($1 \le T_i, L_i \le 10^9$, $L_i \le R_i \le 10^9$).

Print $Q$ lines. On line $i$, print how many bottles are between $L_i$ and $R_i$ inclusive at time $T_i$.