这是一道交互题，仅支持 C++17, C++20。

雅加达有 $N$ 个⽆线电信号塔。这些信号塔排布成⼀条直线，并且从左到右依次编号为从 $0$ 到 $N-1$。 对于每个满足 $0\le i\le N-1$ 的 $i$，信号塔 $i$ 的⾼度为 $H[i]$ ⽶。 所有塔的⾼度都是不同的。

对于某个为正数的信号⼲扰参数 $\delta$，⼀对信号塔 $i$ 和 $j$ $（0\le i<j\le N-1）$ 之间能够互相通信，当且仅当存在⼀个中间信号塔 $k$ 满足如下条件：

• 塔 $i$ 在塔 $k$ 的左边，并且塔 $j$ 在塔 $k$ 的右边，即 $i<k<j$；
• 塔 $i$ 和塔 $j$ 的⾼度都⾄多为 $H[k]-\delta$ ⽶。

Pak Dengklek 想租⼀些信号塔来组建他的新⽆线电⽹络。 你的任务是回答 Pak Dengklek 提出的 $Q$ 个询问。这些询问的形式如下： 给定参数 $L,R$ 和 $D$ $（0\le L\le R\le N-1$ 且 $D>0）$，在满足下述所有条件时，Pak Dengklek 最多能够租多少个信号塔：

• Pak Dengklek 只能租编号在 $L$ 和 $R$ 之间的信号塔（包括 $L$ 和 $R$）；
• 信号⼲扰参数 $\delta$ 的值为 $D$；
• Pak Dengklek 租的信号塔两两之间必须能够进⾏通信。

注意，⽆论中间信号塔 $k$ 是否被租，两个已租的信号塔都可以借助信号塔 $k$ 进⾏通信。

实现细节

你需要实现以下函数：

void init(int N, int[] H)

• $N$： 信号塔的数量。
• $H$： ⼀个⻓度为 $N$ 的数组，给出信号塔的⾼度。
• 这个函数恰好被调⽤⼀次，且在函数 max_towers 的所有调⽤之前。

int max_towers(int L, int R, int D)

• $L,R$：信号塔编号区间的边界。
• $D$：信号⼲扰参数 $\delta$ 的值。
• 该函数应返回 Pak Dengklek 最多能租的信号塔数量（⽤于组建信号⽹络），这⾥ Pak Dengklek 只能租 $L$ 和 $R$ 之间（包含 $L$ 和 $R$）的信号塔，且信号⼲扰参数 $\delta$ 的值是 $D$。
• 该函数将被调⽤恰好 $Q$ 次。

例子

考虑如下函数调⽤序列：

init(7, [10, 20, 60, 40, 50, 30, 70])

max_towers(1, 5, 10)

Pak Dengklek 可以租编号为 $1,3$ 和 $5$ 的信号塔。 下⾯给出了这个例子的示意图，其中的灰色梯形表示被租的信号塔。 信号塔 $3$ 和 $5$ 可以借助信号塔 $4$ 进行通信，这是因为 $40\le 50-10$ 且 $30\le 50-10$。 信号塔 $1$ 和 $3$ 可以借助信号塔 $2$ 进行通信。信号塔 $1$ 和 $5$ 可以借助信号塔 $3$ 进行通信。⽆法租超过 $3$ 个信号塔，因此函数应返回 $3$。

max_towers(2, 2, 100)

在这个区间⾥只有 $1$ 个信号塔，所以 Pak Dengklek 只能租借 $1$ 个信号塔。 因此函数应返回 $1$。

max_towers(0, 6, 17)

Pak Dengklek 可以租信号塔 $1$ 和 $3$。 信号塔 $1$ 和 $3$ 可以借助信号塔 $2$ 进行通信，这是因为 $20\le 60-17$ 且 $40\le 60-17$。 ⽆法租赁超过 $2$ 个信号塔，因此函数应返回 $2$。

约束条件

• $1\le N\le 100000$
• $1\le Q\le 100000$
• $1\le H[i]\le {10}^9$ （对于所有满足 $0\le i\le N-1$ 的 $i$）
• $H[i]\ne H[j]$ （对于所有满足 $0\le i<j\le N-1$ 的 $i$ 和 $j$）
• $0\le L\le R\le N-1$
• $1\le D\le {10}^9$

子任务

1. （$4$ 分） 存在⼀个满足下述所有条件的信号塔 $k$（$0\le k\le N-1$）
   • 对于 $0\le i\le k-1$ 的每个 $i$：$H[i]<H[i+1]$
   • 对于 $k\le i\le N-2$ 的每个 $i$：$H[i]>H[i+1]$
2. （$11$ 分） $Q=1，N\le 2000$
3. （$12$ 分） $Q=1$
4. （$14$ 分） $D=1$
5. （$17$ 分） $L=0，R=N-1$
6. （$19$ 分） $D$ 的值在 max_towers 的所有调⽤中都是相同的
7. （$23$ 分） 没有额外的限制

特别说明：在 uoj 上，这 $7$ 个子任务对应评测结果的后 $7$ 个子任务。

评测程序示例

评测程序示例读取如下格式的输⼊：

• 第 $1$ 行：$NQ$
• 第 $2$ ⾏：$H[0]H[1]\cdots H[N-1]$
• 第 $3+j$ ⾏（$0\le j\le Q-1$）：$LRD$（对应第 $j$ 次询问）

评测程序示例按照如下的格式打印你的答案：

• 第 $1+j$ ⾏（$0\le j\le Q-1$）：max_towers 对第 $j$ 次询问的返回值

时间限制：$2\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$