TP-H3. Barqaror davr

Kompaniya aksiyasining n kunlik narxlari berilgan. Investor «barqaror davr»ni izlaydi: ketma-ket kunlar, ularda eng yuqori va eng past narx farqi K dan oshmaydi. Eng uzun barqaror davr necha kun?

Oynadagi maksimum va minimumni tez bilish uchun ikkita monoton navbat (deque) yuriting.

Kirish ma’lumotlari

Birinchi qatorda n va K, ikkinchisida n ta narx.

Chiqish ma’lumotlari

Bitta son — eng uzun davr uzunligi.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 0 ≤ K ≤ 10⁹; 0 ≤ narx ≤ 10⁹.