Radio Towers

There are $N$ radio towers in Jakarta.
The towers are located along a straight line and numbered from $0$ to $N - 1$ from left to right.
For each $i$ such that $0 \le i \le N - 1$, the height of tower $i$ is $H[i]$ metres.
The heights of the towers are distinct.

For some positive interference value $\delta$, a pair of towers $i$ and $j$ (where $0 \le i \lt j \le N - 1$) can communicate with each other if and only if there is an intermediary tower $k$, such that
* tower $i$ is to the left of tower $k$ and tower $j$ is to the right of tower $k$, that is, $i \lt k \lt j$, and
* the heights of tower $i$ and tower $j$ are both at most $H[k] - \delta$ metres.

Pak Dengklek wants to lease some radio towers for his new radio network.
Your task is to answer $Q$ questions of Pak Dengklek which are of the following form:
given parameters $L, R$ and $D$ ($0 \le L \le R \le N - 1$ and $D > 0$), what is the maximum number of towers Pak Dengklek can lease, assuming that
* Pak Dengklek can only lease towers with indices between $L$ and $R$ (inclusive), and
* the interference value $\delta$ is $D$, and
* any pair of radio towers that Pak Dengklek leases must be able to communicate with each other.

Note that two leased towers may communicate using an intermediary tower $k$, regardless of whether tower $k$ is leased or not.

Implementation Details

You should implement the following procedures:

void init(int N, int[] H)

• $N$: the number of radio towers.
• $H$: an array of length $N$ describing the tower heights.
• This procedure is called exactly once, before any calls to max_towers.

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

• $L$, $R$: the boundaries of a range of towers.
• $D$: the value of $\delta$.
• This procedure should return the maximum number of radio towers Pak Dengklek can lease for his new radio network if he is only allowed to lease towers between tower $L$ and tower $R$ (inclusive) and the value of $\delta$ is $D$.
• This procedure is called exactly $Q$ times.

Example

Consider the following sequence of calls:

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

max_towers(1, 5, 10)

Pak Dengklek can lease towers $1$, $3$, and $5$.
The example is illustrated in the following picture, where shaded trapezoids represent leased towers.

Towers $3$ and $5$ can communicate using tower $4$ as an intermediary, since $40 \le 50 - 10$ and $30 \le 50 - 10$.
Towers $1$ and $3$ can communicate using tower $2$ as an intermediary.
Towers $1$ and $5$ can communicate using tower $3$ as an intermediary.
There is no way to lease more than $3$ towers, therefore the procedure should return $3$.

max_towers(2, 2, 100)

There is only $1$ tower in the range, thus Pak Dengklek can only lease $1$ tower.
Therefore the procedure should return $1$.

max_towers(0, 6, 17)

Pak Dengklek can lease towers $1$ and $3$.
Towers $1$ and $3$ can communicate using tower $2$ as an intermediary, since $20 \le 60 - 17$ and $40 \le 60 - 17$.
There is no way to lease more than $2$ towers, therefore the procedure should return $2$.

Constraints

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le H[i] \le 10^9$ (for each $i$ such that $0 \le i \le N - 1$)
• $H[i] \ne H[j]$ (for each $i$ and $j$ such that $0 \le i \lt j \le N - 1$)
• $0 \le L \le R \le N - 1$
• $1 \le D \le 10^9$

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N \; Q$
• line $2$: $H[0] \; H[1] \; \ldots \; H[N - 1]$
• line $3 + j$ ($0 \le j \le Q - 1$): $L \; R \; D$ for question $j$

The sample grader prints your answers in the following format:

• line $1 + j$ ($0 \le j \le Q - 1$): the return value of max_towers for question $j$

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Radio Towers)

There are $N$ radio towers in Jakarta.
The towers are located along a straight line and numbered from $0$ to $N - 1$ from left to right.
For each $i$ such that $0 \le i \le N - 1$, the height of tower $i$ is $H[i]$ metres.
The heights of the towers are distinct.

For some positive interference value $\delta$, a pair of towers $i$ and $j$ (where $0 \le i \lt j \le N - 1$) can communicate with each other if and only if there is an intermediary tower $k$, such that
* tower $i$ is to the left of tower $k$ and tower $j$ is to the right of tower $k$, that is, $i \lt k \lt j$, and
* the heights of tower $i$ and tower $j$ are both at most $H[k] - \delta$ metres.

Pak Dengklek wants to lease some radio towers for his new radio network.
Your task is to answer $Q$ questions of Pak Dengklek which are of the following form:
given parameters $L, R$ and $D$ ($0 \le L \le R \le N - 1$ and $D > 0$), what is the maximum number of towers Pak Dengklek can lease, assuming that
* Pak Dengklek can only lease towers with indices between $L$ and $R$ (inclusive), and
* the interference value $\delta$ is $D$, and
* any pair of radio towers that Pak Dengklek leases must be able to communicate with each other.

Note that two leased towers may communicate using an intermediary tower $k$, regardless of whether tower $k$ is leased or not.

Implementation Details

You should implement the following procedures:

void init(int N, int[] H)

• $N$: the number of radio towers.
• $H$: an array of length $N$ describing the tower heights.
• This procedure is called exactly once, before any calls to max_towers.

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

• $L$, $R$: the boundaries of a range of towers.
• $D$: the value of $\delta$.
• This procedure should return the maximum number of radio towers Pak Dengklek can lease for his new radio network if he is only allowed to lease towers between tower $L$ and tower $R$ (inclusive) and the value of $\delta$ is $D$.
• This procedure is called exactly $Q$ times.

Example

Consider the following sequence of calls:

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

max_towers(1, 5, 10)

Pak Dengklek can lease towers $1$, $3$, and $5$.
The example is illustrated in the following picture, where shaded trapezoids represent leased towers.

Towers $3$ and $5$ can communicate using tower $4$ as an intermediary, since $40 \le 50 - 10$ and $30 \le 50 - 10$.
Towers $1$ and $3$ can communicate using tower $2$ as an intermediary.
Towers $1$ and $5$ can communicate using tower $3$ as an intermediary.
There is no way to lease more than $3$ towers, therefore the procedure should return $3$.

max_towers(2, 2, 100)

There is only $1$ tower in the range, thus Pak Dengklek can only lease $1$ tower.
Therefore the procedure should return $1$.

max_towers(0, 6, 17)

Pak Dengklek can lease towers $1$ and $3$.
Towers $1$ and $3$ can communicate using tower $2$ as an intermediary, since $20 \le 60 - 17$ and $40 \le 60 - 17$.
There is no way to lease more than $2$ towers, therefore the procedure should return $2$.

Constraints

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le H[i] \le 10^9$ (for each $i$ such that $0 \le i \le N - 1$)
• $H[i] \ne H[j]$ (for each $i$ and $j$ such that $0 \le i \lt j \le N - 1$)
• $0 \le L \le R \le N - 1$
• $1 \le D \le 10^9$

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N \; Q$
• line $2$: $H[0] \; H[1] \; \ldots \; H[N - 1]$
• line $3 + j$ ($0 \le j \le Q - 1$): $L \; R \; D$ for question $j$

The sample grader prints your answers in the following format:

• line $1 + j$ ($0 \le j \le Q - 1$): the return value of max_towers for question $j$

Execution limits

Your solution will have 2.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "towers.h"

#include <vector>

void init(int N, std::vector<int> H) {

}

int max_towers(int L, int R, int D) {
  return 0;
}

参考代码

#include "towers.h"

#include <vector>

void init(int N, std::vector<int> H) {

}

int max_towers(int L, int R, int D) {
  return 0;
}

请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。

本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。

由 manager 进程打印判定结果，无需自行写出答案。

include "towers.h"

include <vector>

void init(int N, std::vector<int> H) {

}

int max_towers(int L, int R, int D) {
return 0;
}