在 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$($1 \le j \le Q$),站在座標介於 $L_j$ 到 $R_j$ 之間(含兩端)的人數。
任務
給定每名選手的遲緩度以及 $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