{"raw_statement":[{"iden":"background","content":"\n\n### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。\n\n这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。"},{"iden":"statement","content":"雅加达有 $N$ 个无线电信号塔。这些信号塔排布成一条直线，并且从左到右依次编号为从 $0$ 到 $N - 1$。\n对于每个满足 $0 \\le i \\le N - 1$ 的 $i$，信号塔 $i$ 的高度为 $H_i$ 米。\n所有塔的高度都是**不同的**。\n\n对于某个为正数的信号干扰参数 $\\delta$，一对信号塔 $i$ 和 $j$ ($0 \\le i \\lt j \\le N - 1$) 之间能够互相通信，当且仅当存在一个中间信号塔 $k$ 满足如下条件：\n\n* 塔 $i$ 在塔 $k$ 的左边，并且塔 $j$ 在塔 $k$ 的右边，即 $i \\lt k \\lt j$；\n* 塔 $i$ 和塔 $j$ 的高度都至多为 $H[k] - \\delta$ 米。\n\nPak Dengklek 想租一些信号塔来组建他的新无线电网络。\n你的任务是回答 Pak Dengklek 提出的 $Q$ 个询问。这些询问的形式如下：\n给定参数 $L, R$ 和 $D$ ($0 \\le L \\le R \\le N - 1$ 且 $D > 0$)，在满足下述所有条件时，Pak Dengklek 最多能够租多少个信号塔：\n\n * Pak Dengklek 只能租编号在 $L$ 和 $R$ 之间的信号塔（包括 $L$和 $R$）；\n * 信号干扰参数 $\\delta$ 的值为 $D$；\n * Pak Dengklek 租的信号塔两两之间必须能够进行通信。\n\n注意，无论中间信号塔 $k$ 是否被租，两个已租的信号塔都可以借助信号塔 $k$ 进行通信。"},{"iden":"input","content":"你需要实现以下函数：\n\n```go\nvoid init(int N, int[] H)\n```\n\n* $N$： 信号塔的数量。\n* $H$： 一个长度为 $N$ 的数组，给出信号塔的高度。\n* 这个函数恰好被调用一次，且在函数 `max_towers` 的所有调用之前。\n\n```go\nint max_towers(int L, int R, int D)\n```\n\n* $L$, $R$：信号塔编号区间的边界。\n* $D$：信号干扰参数 $\\delta$ 的值。\n* 该函数应返回 Pak Dengklek 最多能租的信号塔数量（用于组建信号网络），这里 Pak Dengklek 只能租 $L$ 和 $R$之间（包含 $L$ 和 $R$）的信号塔，且信号干扰参数 $\\delta$ 的值是 $D$。\n* 该函数将被调用恰好 $Q$ 次。"},{"iden":"output","content":"考虑如下函数调⽤序列：\n\n```go\ninit(7, [10, 20, 60, 40, 50, 30, 70])\n```\n\n```go\nmax_towers(1, 5, 10)\n```\n\nPak Dengklek 可以租编号为 $1$, $3$ 和 $5$ 的信号塔。\n下面给出了这个例子的示意图，其中的灰色梯形表示被租的信号塔。\n\n![](https://img.loj.ac.cn/2022/08/10/a52f5b077031b.png)\n\n信号塔 $3$ 和 $5$ 可以借助信号塔 $4$ 进行通信，这是因为 $40 \\le 50 - 10$ 且 $30 \\le 50 - 10$。\n信号塔 $1$ 和 $3$ 可以借助信号塔 $2$ 进行通信。\n信号塔 $1$ 和 $5$ 可以借助信号塔 $3$ 进行通信。\n无法租超过 $3$ 个信号塔，因此函数应返回 $3$。\n\n```go\nmax_towers(2, 2, 100)\n```\n\n在这个区间里只有 $1$ 个信号塔，所以 Pak Dengklek 只能租借 $1$ 个信号塔。\n因此函数应返回 $1$。\n\n```go\nmax_towers(0, 6, 17)\n```\n\nPak Dengklek 可以租信号塔$1$ 和 $3$ 。\n信号塔  $1$ 和 $3$ 可以借助信号塔 $2$进行通信，这是因为 $20 \\le 60 - 17$ 且 $40 \\le 60 - 17$。\n无法租赁超过 $2$ 个信号塔，因此函数应返回 $2$。"},{"iden":"note","content":"### 约束条件\n\n* $1 \\le N \\le 100\\;000$\n* $1 \\le Q \\le 100\\;000$\n* $1 \\le H_i \\le 10^9$ (对于所有满足 $0 \\le i \\le N - 1$ 的 $i$ )\n* $H_i \\ne H_j$ (对于所有满足 $0 \\le i \\lt j \\le N - 1$  的 $i$ 和 $j$ )\n* $0 \\le L \\le R \\le N - 1$\n* $1 \\le D \\le 10^9$\n\n### 子任务\n\n1. (4 分) 存在一个满足下述所有条件的信号塔 $k$ ($0 \\le k \\le N - 1$) \n   * 对于 $0 \\le i \\le k - 1$ 的每个 $i$：$H_i \\lt H_{i + 1}$ \n   * 对于 $k \\le i \\le N - 2$ 的每个 $i$：$H_i \\gt H_{i + 1}$ \n2. (11 分) $Q = 1$，$N \\le 2000$\n3. (12 分) $Q = 1$\n4. (14 分) $D = 1$\n5. (17 分) $L = 0$，$R = N - 1$\n6. (19 分)  $D$ 的值在 `max_towers` 的所有调用中都是相同的\n7. (23 分) 没有额外的限制\n\n### 评测程序示例\n\n评测程序示例读取如下格式的输入：\n\n* 第 $1$ 行：$N \\; Q$\n* 第 $2$ 行：$H_{0} \\; H_{1} \\; \\ldots \\; H_{N - 1}$\n* 第 $3 + j$ 行（$0 \\le j \\le Q - 1$）：$L \\; R \\; D$（对应第 $j$ 次询问）\n\n评测程序示例按照如下的格式打印你的答案：\n\n* 第 $1 + j$ 行（$0 \\le j \\le Q - 1$）：`max_towers` 对第 $j$ 次询问的返回值\n\n### 约定\n\n题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。\n\n在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：\n\n| `void ` | `int` | `int64`     | `int[]`            |\n| ------- | ----- | ----------- | ------------------ |\n| `void ` | `int` | `long long` | `std::vector<int>` |\n\n| `int[][]`                       | 数组 `a` 的长度 |\n| ------------------------------- | ------------------- |\n| `std::vector<std::vector<int>>` | `a.size()`          |\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}