Có \(N\) tháp phát thanh ở Jakarta. Các tháp nằm dọc theo một đường thẳng và được đánh số từ \(0\) đến \(N - 1\) từ trái sang phải. Với mỗi \(i\) sao cho \(0 \le i \le N - 1\), chiều cao của tháp \(i\) là \(H[i]\) mét. Chiều cao của các tháp là phân biệt.

Đối với một giá trị nhiễu \(\delta\) dương nào đó, một cặp tháp \(i\) và \(j\) (trong đó \(0 \le i < j \le N - 1\)) có thể giao tiếp với nhau khi và chỉ khi có một tháp trung gian \(k\), sao cho

• tháp \(i\) ở bên trái tháp \(k\) và tháp \(j\) ở bên phải tháp \(k\), tức là \(i < k < j\), và
• chiều cao của tháp \(i\) và tháp \(j\) đều cao không quá là \(H[k] - \delta\) mét.

Pak Dengklek muốn thuê một số tháp cho mạng phát thanh mới của mình.
Nhiệm vụ của bạn là trả lời \(Q\) câu hỏi của Pak Dengklek có dạng như sau:
cho trước các tham số \(L, R\) và \(D\) (\(0 \le L \le R \le N - 1\) và \(D > 0\)), số lượng tháp tối đa mà Pak Dengklek có thể thuê là bao nhiêu, giả sử rằng

• Pak Dengklek chỉ có thể thuê các tháp có chỉ số từ \(L\) đến \(R\) (bao gồm cả hai đầu mút), và
• giá trị nhiễu \(\delta\) là \(D\), và
• bất kỳ cặp tháp phát thanh nào mà Pak Dengklek thuê phải có khả năng giao tiếp với nhau.

Lưu ý rằng hai tháp đã thuê có thể giao tiếp bằng cách sử dụng tháp trung gian \(k\), bất kể tháp \(k\) có được thuê hay không.

Chi tiết cài đặt

Bạn cần cài đặt các hàm sau:

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

• \(N\): số lượng tháp phát thanh.
• \(H\): một mảng có độ dài \(N\) mô tả chiều cao của các tháp.
• Hàm này được gọi đúng một lần, trước bất kỳ lệnh gọi nào đến max_towers.

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

• \(L\), \(R\): ranh giới của các tháp.
• \(D\): giá trị của \(\delta\).
• Hàm này sẽ trả lại số lượng lớn nhất các tháp phát thanh mà Pak Dengklek có thể thuê cho mạng phát thanh mới của mình nếu anh ta chỉ được phép thuê các tháp giữa tháp \(L\) và tháp \(R\) (bao gồm cả hai đầu mút) và giá trị của \(\delta\) là \(D\).
• Hàm này được gọi đúng là \(Q\) lần.

Ví dụ

Hãy xem xét dãy các lời gọi sau:

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

max_towers(1, 5, 10)

Pak Dengklek có thể thuê tháp \(1\), \(3\) và \(5\).
Ví dụ được minh họa trong hình sau, trong đó các hình thang được tô đậm thể hiện cho các tháp được thuê.

Tháp \(3\) và \(5\) có thể giao tiếp bằng cách sử dụng tháp \(4\) làm trung gian, vì \(40 \le 50 - 10\) và \(30 \le 50 - 10\). Các tháp \(1\) và \(3\) có thể giao tiếp bằng cách sử dụng tháp \(2\) làm trung gian. Tháp \(1\) và \(5\) có thể giao tiếp bằng cách sử dụng tháp \(3\) làm trung gian.
Không có cách nào để thuê được nhiều hơn \(3\) tháp, do đó hàm phải trả lại \(3\).

max_towers(2, 2, 100)

Có duy nhất tháp \(1\) trong phạm vi, do đó Pak Dengklek chỉ có thể thuê tháp \(1\).
Vì vậy, thủ tục sẽ trả về \(1\).

max_towers(0, 6, 17)

Pak Dengklek có thể thuê tháp \(1\) và \(3\).
Các tháp \(1\) và \(3\) có thể giao tiếp bằng cách sử dụng tháp \(2\) làm trung gian, vì \(20 \le 60 - 17\) and \(40 \le 60 - 17\). Không có cách nào để thuê nhiều hơn \(2\) tháp, do đó hàm phải trả lại \(2\).

Ràng buộc

• \(1 \le N \le 100\;000\)
• \(1 \le Q \le 100\;000\)
• \(1 \le H[i] \le 10^9\) (với mỗi \(i\) sao cho \(0 \le i \le N - 1\))
• \(H[i] \ne H[j]\) (với mỗi \(i\) và \(j\) sao cho \(0 \le i < j \le N - 1\))
• \(0 \le L \le R \le N - 1\)
• \(1 \le D \le 10^9\)

Phân nhóm

1. (4 điểm) Tồn tại một tháp \(k\) (\(0 \le k \le N - 1\)) sao cho
   • với mỗi \(i\) sao cho \(0\le i\le k-1\): \(H[i] < H[i + 1]\), và
   • với mỗi \(i\) sao cho \(k \le i \le N - 2\): \(H[i] > H[i + 1]\).
2. (11 điểm) \(Q = 1\), \(N \le 2000\)
3. (12 điểm) \(Q = 1\)
4. (14 điểm) \(D = 1\)
5. (17 điểm) \(L = 0\), \(R = N - 1\)
6. (19 điểm) Giá trị của \(D\) giống nhau trong tất cả các lần gọi hàm max_towers.
7. (23 điểm) Không có ràng buộc nào thêm.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng:

• dòng \(1\): \(N \; Q\)
• dòng \(2\): \(H[0] \; H[1] \; \ldots \; H[N - 1]\)
• dòng \(3 + j\) (\(0 \le j \le Q - 1\)): \(L \; R \; D\) với câu hỏi \(j\)

Trình chấm mẫu in các kết quả của bạn theo định dạng:

• dòng \(1 + j\) (\(0 \le j \le Q - 1\)): giá trị trả về của max_towers cho câu hỏi \(j\)

Nguồn: Đề thi tiếng Việt IOI 2022, giấy phép CC-BY.