在 IOI 2018 的開幕典禮上，$N$ 位選手排成一列前進，這條直線以數線表示。所有選手都朝數線的正方向前進。在時刻 $0$，從前方數來的第 $i$ 位選手（$1 \le i \le N$）站在座標 $-i$。此外，掌旗手 IOI-chan 站在座標 $0$。

每位選手都有一個稱為遲緩度的數值。第 $i$ 位選手的遲緩度為 $D_i$。選手遵守以下規則：

• 如果第 $i$ 位選手與正前方的人（另一位選手或 IOI-chan）之間的距離大於或等於 $D_i+1$，第 $i$ 位選手就移動到與那個人相距 $1$ 的位置。否則，第 $i$ 位選手不移動。

IOI-chan 每單位時間沿數線的正方向移動距離 $1$。每當上述條件滿足時，選手都會瞬間移動。

你是負責報導開幕典禮的記者。你本來應該拍照，卻在整場典禮中睡得很熟。事到如今也沒有辦法——你決定作弊，先拍攝會場，再在照片上畫出人們。

為了不讓作弊被發現，或為了估計畫圖所需的時間，你想知道以下 $Q$ 個數值：

• 在時刻 $T_j$，站在座標 $L_j$ 到 $R_j$ 之間（包含兩端）的人數（$1 \le j \le Q$）。

任務

給定每位選手的遲緩度與 $Q$ 個問題的資料，請撰寫程式，對每個問題計算滿足條件的人數。

輸入格式

從標準輸入讀取以下資料。

• 輸入的第一行包含兩個以空格分隔的整數 $N$ 和 $Q$。這表示有 $N$ 位選手（不包含 IOI-chan），以及 $Q$ 個問題。
• 接下來 $N$ 行中的第 $i$ 行（$1 \le i \le N$）包含一個整數 $D_i$。這表示從前方數來的第 $i$ 位選手的遲緩度為 $D_i$。
• 接下來 $Q$ 行中的第 $j$ 行（$1 \le j \le Q$）包含三個以空格分隔的整數 $T_j$、$L_j$ 和 $R_j$。這些數值表示第 $j$ 個問題。

輸出格式

向標準輸出寫入 $Q$ 行。輸出的第 $j$ 行（$1 \le j \le Q$）應包含第 $j$ 個問題的答案。

資料範圍

所有輸入資料都滿足以下條件。

• $1 \le N \le 500\,000$。
• $1 \le Q \le 500\,000$。
• $1 \le D_i \le 1\,000\,000\,000$（$1 \le i \le N$）。
• $1 \le T_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。
• $1 \le L_j \le R_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。

子任務

共有 3 個子任務。各子任務的配分與額外限制如下：

子任務 1 [7 分]

• $D_i=1$（$1 \le i \le N$）。

子任務 2 [12 分]

• $N \le 1\,000$。
• $Q \le 1\,000$。
• $T_j \le 1\,000$（$1 \le j \le Q$）。
• $1 \le L_j \le R_j \le 1\,000$（$1 \le j \le Q$）。

子任務 3 [81 分]

沒有額外限制。

範例

輸入格式 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

輸出格式 1

0
1
1
2
1
2

說明

在這組範例輸入中，選手與 IOI-chan 的移動情況如下。

以下以區間 $[L,R]$ 表示數線上座標介於 $L$ 與 $R$ 之間（包含兩端）的點所組成的集合。

• 在時刻 $0$，IOI-chan 站在座標 $0$。第 1、2、3 位選手分別站在座標 $-1$、$-2$、$-3$。
• 在時刻 $1$，IOI-chan 移動到座標 $1$。沒有選手移動；第 1、2、3 位選手分別站在座標 $-1$、$-2$、$-3$。由於區間 $[2,4]$ 中沒有人，第 1 個問題輸出 $0$。
• 在時刻 $2$，IOI-chan 移動到座標 $2$。此時 IOI-chan 與第 1 位選手的距離為 $3$，因此第 1 位選手移動到座標 $1$。第 1、2、3 位選手分別站在座標 $1$、$-2$、$-3$。由於區間 $[2,4]$ 中只有 IOI-chan，第 2 個問題輸出 $1$。
• 在時刻 $3$，IOI-chan 移動到座標 $3$。沒有選手移動；第 1、2、3 位選手分別站在座標 $1$、$-2$、$-3$。由於區間 $[2,4]$ 中只有 IOI-chan，第 3 個問題輸出 $1$。
• 在時刻 $4$，IOI-chan 移動到座標 $4$。此時 IOI-chan 與第 1 位選手的距離為 $3$，因此第 1 位選手移動到座標 $3$。第 1、2、3 位選手分別站在座標 $3$、$-2$、$-3$。由於區間 $[2,4]$ 中有 IOI-chan 與第 1 位選手，第 4 個問題輸出 $2$。
• 在時刻 $5$，IOI-chan 移動到座標 $5$。沒有選手移動；第 1、2、3 位選手分別站在座標 $3$、$-2$、$-3$。由於區間 $[2,4]$ 中只有第 1 位選手，第 5 個問題輸出 $1$。
• 在時刻 $6$，IOI-chan 移動到座標 $6$。此時 IOI-chan 與第 1 位選手的距離為 $3$，因此第 1 位選手移動到座標 $5$。接著，第 1 位與第 2 位選手的距離變成 $7$，因此第 2 位選手移動到座標 $4$。此外，第 2 位與第 3 位選手的距離變成 $7$，因此第 3 位選手移動到座標 $3$。第 1、2、3 位選手分別站在座標 $5$、$4$、$3$。由於區間 $[2,4]$ 中有第 2 位與第 3 位選手，第 6 個問題輸出 $2$。

輸入格式 2

4 2
1
1
1
1
2 1 4
1 3 6

輸出格式 2

2
0

說明

這組範例輸入滿足子任務 1 的限制。

輸入格式 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

輸出格式 3

1
6
0
5
2
7