Ραδιοφωνικοί Πύργοι

Υπάρχουν ~N~ πύργοι ραδιοφώνου στην Τζακάρτα. Οι πύργοι βρίσκονται κατά μήκος μιας ευθείας γραμμής και αριθμούνται από ~0~ έως ~N - 1~ από αριστερά προς τα δεξιά. Για κάθε ~i~ τέτοιο ώστε ~0 \le i \le N - 1~, το ύψος του πύργου ~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 θέλει να μισθώσει μερικούς ραδιοφωνικούς πύργους για το νέο του ραδιοφωνικό δίκτυο. Ο στόχος σας είναι να απαντήσετε σε ~Q~ ερωτήσεις του Pak Dengklek που έχουν την ακόλουθη μορφή: δίδονται οι παράμετροι ~L, R~ και ~D~ (~0 \le L \le R \le N - 1~ και ~D > 0~), ποιος είναι ο μέγιστος αριθμός πύργων που μπορεί να μισθώσει ο Pak Dengklek, υποθέτοντας ότι

• Ο Pak Dengklek μπορεί να μισθώσει μόνο πύργους με δείκτες μεταξύ ~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 για το νέο του ραδιοφωνικό δίκτυο, εάν του επιτρέπεται να μισθώνει πύργους μόνο μεταξύ του πύργου ~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 100\;000~
• ~1 \le Q \le 100\;000~
• ~1 \le H[i] \le 10^9~ (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le N - 1~)
• ~H[i] \ne H[j]~ (για κάθε ~i~ και ~j~ τέτοια ώστε ~0 \le i < j \le N - 1~)
• ~0 \le L \le R \le N - 1~
• ~1 \le D \le 10^9~

Υποπροβλήματα

1. (4 βαθμοί) Υπάρχει ένας πύργος ~k~ (~0 \le k \le N - 1~) όπου
   • για κάθε ~i~ τέτοιο ώστε ~0\le i\le k-1~ : ~H[i] < H[i + 1]~, και
   • για κάθε ~i~ τέτοιο ώστε ~k \le i \le N - 2~ : ~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 βαθμοί) Κανένας επιπλέον περιορισμός.

Υπόδειγμα Βαθμολογητή

Ο βαθμολογητής διαβάζει την είσοδο στην ακόλουθη μορφή:

• γραμμή ~1~: ~N \; Q~
• γραμμή ~2~: ~H[0] \; H[1] \; \ldots \; H[N - 1]~
• γραμμή ~3 + j~ (~0 \le j \le Q - 1~) : ~L \; R \; D~ για την ερώτηση ~j~

Ο βαθμολογητής εκτυπώνει την απάντηση στην ακόλουθη μορφή:

• γραμμή ~1 + j~ (~0 \le j \le Q - 1~) : η επιστρεφόμενη τιμή της max_towers για την ερώτηση ~j~