喺 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