Background

Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem.

This is an interactive problem. You only need to implement the functions required in the code.

Your code does not need to include any additional header files, and you do not need to implement the main function.

Problem Description

There are $N$ radio signal towers in Jakarta. These towers are arranged in a straight line and are numbered from $0$ to $N - 1$ from left to right.
For each $i$ satisfying $0 \le i \le N - 1$, tower $i$ has height $H_i$ meters.
All tower heights are distinct.

For a positive signal interference parameter $\delta$, a pair of towers $i$ and $j$ ($0 \le i \lt j \le N - 1$) can communicate with each other if and only if there exists an intermediate tower $k$ such that:

• Tower $i$ is to the left of tower $k$, and tower $j$ is to the right of tower $k$, i.e., $i \lt k \lt j$;
• The heights of towers $i$ and $j$ are both at most $H[k] - \delta$ meters.

Pak Dengklek wants to rent some towers to build his new radio network.
Your task is to answer $Q$ queries from Pak Dengklek. Each query is as follows:
Given $L$, $R$, and $D$ ($0 \le L \le R \le N - 1$ and $D > 0$), determine the maximum number of towers Pak Dengklek can rent, subject to all of the following conditions:

• Pak Dengklek can only rent towers with indices between $L$ and $R$ (inclusive);
• The signal interference parameter $\delta$ equals $D$;
• Every pair of rented towers must be able to communicate with each other.

Note that regardless of whether the intermediate tower $k$ is rented, two rented towers can still use tower $k$ to communicate.

Input Format

You need to implement the following functions:

void init(int N, int[] H)

• $N$: the number of towers.
• $H$: an array of length $N$ giving the heights of the towers.
• This function is called exactly once, and before any calls to max_towers.

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

• $L$, $R$: the boundaries of the tower index range.
• $D$: the value of the signal interference parameter $\delta$.
• This function should return the maximum number of towers Pak Dengklek can rent (to build the radio network), where Pak Dengklek can only rent towers between $L$ and $R$ (inclusive), and the signal interference parameter $\delta$ equals $D$.
• This function will be called exactly $Q$ times.

Output Format

Consider the following sequence of function calls:

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

max_towers(1, 5, 10)

Pak Dengklek can rent towers $1$, $3$, and $5$.
The diagram below illustrates this example, where the gray trapezoids represent the rented towers.

Towers $3$ and $5$ can communicate using tower $4$, because $40 \le 50 - 10$ and $30 \le 50 - 10$.
Towers $1$ and $3$ can communicate using tower $2$.
Towers $1$ and $5$ can communicate using tower $3$.
It is impossible to rent more than $3$ towers, so the function should return $3$.

max_towers(2, 2, 100)

There is only $1$ tower in this range, so Pak Dengklek can only rent $1$ tower.
Therefore, the function should return $1$.

max_towers(0, 6, 17)

Pak Dengklek can rent towers $1$ and $3$.
Towers $1$ and $3$ can communicate using tower $2$, because $20 \le 60 - 17$ and $40 \le 60 - 17$.
It is impossible to rent more than $2$ towers, so the function should return $2$.

Hint

Constraints

• $1 \le N \le 100\;000$
• $1 \le Q \le 100\;000$
• $1 \le H_i \le 10^9$ (for all $i$ satisfying $0 \le i \le N - 1$)
• $H_i \ne H_j$ (for all $i$ and $j$ satisfying $0 \le i \lt j \le N - 1$)
• $0 \le L \le R \le N - 1$
• $1 \le D \le 10^9$

Subtasks

1. (4 points) There exists a tower $k$ ($0 \le k \le N - 1$) satisfying all of the following:
   • For each $i$ with $0 \le i \le k - 1$: $H_i \lt H_{i + 1}$
   • For each $i$ with $k \le i \le N - 2$: $H_i \gt H_{i + 1}$
2. (11 points) $Q = 1$, $N \le 2000$
3. (12 points) $Q = 1$
4. (14 points) $D = 1$
5. (17 points) $L = 0$, $R = N - 1$
6. (19 points) The value of $D$ is the same in all calls to max_towers
7. (23 points) No additional constraints

Sample grader

The sample grader reads 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$ (corresponding to the $j$-th query)

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 the $j$-th query

Notes

In the statement, the function interfaces use general type names void, int, int64, int[] (array), and int[][] (array of arrays).

In C++, the grader will use appropriate data types or implementations, as shown in the tables below:

Translated by ChatGPT 5