# Fernsehtürme In Jakarta befinden sich $N$ Fernsehtürme. Alle Türme stehen in einer Reihe und sind durchnummeriert von $0$ bis $N - 1$ von links nach rechts. Turm $i$ ist $H[i]$ Meter hoch, für alle $i$ mit $0 \le i \le N - 1$. Alle Höhen sind **unterschiedlich**. Für einen positiven *Interferenzwert* $\delta$ können Türme $i$ und $j$ ($0 \le i \lt j \le N - 1$) genau dann miteinander kommunizieren, wenn ein Turm $k$ dazwischen steht, sodass: * Turm $i$ steht links von Turm $k$, und Turm $j$ steht rechts von Turm $k$, also $i \lt k \lt j$, sowie * Türme $i$ und $j$ sind beide höchstens $H[k] - \delta$ Meter hoch. Pak Dengklek möchte einige Fernsehtürme für sein neues Telekommunikationsnetz mieten. Deine Aufgabe ist es, $Q$ Abfragen für Pak Dengklek zu beantworten, alle in folgender Form: Gegeben Parameter $L, R$ und $D$ ($0 \le L \le R \le N - 1$ und $D > 0$), was ist die maximale Anzahl an Türmen, die Pak Dengklek mieten kann, unter den folgenden Bedingungen: * Nur Türme mit Index von $L$ bis inklusive $R$ können gemietet werden. * Der Interferenzwert $\delta$ ist $D$. * Alle gemieteten Türme müssen paarweise miteinander kommunizieren können. Beachte, dass zwei gemietete Türme über Turm $k$ kommunizieren dürfen, unabhängig davon, ob Turm $k$ gemietet ist oder nicht. ## Implementierungsdetails Implementiere folgende Funktionen: ``` void init(int N, int[] H) ``` * $N$: Die Anzahl an Fernsehtürmen. * $H$: Ein Array der Länge $N$ mit den Höhen der Türme. * Die Funktion wird genau einmal aufgerufen, und zwar vor allen Aufrufen von `max_towers`. ``` int max_towers(int L, int R, int D) ``` * $L$, $R$: Nur Fernsehtürme von $L$ bis inklusive $R$ können gemietet werden. * $D$: Der Wert von $\delta$. * Diese Funktion soll die maximale Anzahl an Fernsehtürmen zurückgeben, die Pak Dengklek für sein Telekommunikationsnetz mieten kann, wenn er nur Türme von $L$ bis inklusive $R$ mieten kann und $\delta$ den Wert $D$ hat. * Diese Funktion wird genau $Q$ Mal aufgerufen. ## Beispiel Betrachte die folgende Folge von Aufrufen: ``` init(7, [10, 20, 60, 40, 50, 30, 70]) ``` ``` max_towers(1, 5, 10) ``` Pak Dengklek kann die Türme $1$, $3$ und $5$ mieten. Das Beispiel ist im folgenden Bild dargestellt, wobei die gemieteten Türme in dunkelgrau markiert sind. ![](towers-example.png) Türme $3$ und $5$ können über Turm $4$ kommunizieren, weil $40 \le 50 - 10$ und $30 \le 50 - 10$. Türme $1$ und $3$ können über Turm $2$ kommunizieren. Türme $1$ und $5$ können über Turm $3$ kommunizieren. Es ist nicht möglich, mehr als $3$ Türme zu mieten, deshalb muss die Funktion $3$ zurückgeben.
``` max_towers(2, 2, 100) ``` Es gibt nur $1$ Turm im erlaubten Bereich, deshalb kann Pak Dengklek nur $1$ Turm mieten. Die Funktion muss daher $1$ zurückgeben. ``` max_towers(0, 6, 17) ``` Pak Dengklek kann Türme $1$ und $3$ mieten. Türme $1$ und $3$ können über $2$ kommunizieren, weil $20 \le 60 - 17$ und $40 \le 60 - 17$. Es ist nicht möglich, mehr als $2$ Türme zu mieten, deshalb muss die Funktion $2$ zurückgeben. ## Beschränkungen * $1 \le N \le 100\;000$ * $1 \le Q \le 100\;000$ * $1 \le H[i] \le 10^9$ (für alle $i$ mit $0 \le i \le N - 1$) * $H[i] \ne H[j]$ (für alle $i$ und $j$ mit $0 \le i \lt j \le N - 1$) * $0 \le L \le R \le N - 1$ * $1 \le D \le 10^9$ ## Teilaufgaben 1. (4 Punkte) Es existiert ein Turm $k$ ($0 \le k \le N - 1$) sodass * für alle $i$ mit $0\le i\le k-1$ gilt $H[i] \lt H[i + 1]$, und * für alle $i$ mit $k \le i \le N - 2$ gilt $H[i] \gt H[i + 1]$. 1. (11 Punkte) $Q = 1$, $N \le 2000$ 1. (12 Punkte) $Q = 1$ 1. (14 Punkte) $D = 1$ 1. (17 Punkte) $L = 0$, $R = N - 1$ 1. (19 Punkte) Der Wert von $D$ ist in allen Abfragen gleich. 1. (23 Punkte) Keine weiteren Beschränkungen. ## Sample-Grader Der Sample-Grader liest die Eingabe im folgenden Format: * Zeile $1$: $N \; Q$ * Zeile $2$: $H[0] \; H[1] \; \ldots \; H[N - 1]$ * Zeile $3 + j$ ($0 \le j \le Q - 1$): $L \; R \; D$ für Abfrage $j$ Der Sample-Grader gibt deine Antworten in folgendem Format aus: * Zeile $1 + j$ ($0 \le j \le Q - 1$): der Rückgabewert von `max_towers` für Abfrage $j$