E. Issiqxona

Biologiya to‘garagi litsey issiqxonasida noyob ko‘chat o‘stirmoqda. Datchik har daqiqada haroratni yozib boradi: i-daqiqada harorat tᵢ gradus bo‘lgan, jami N ta o‘lchov.

Ko‘chat uchun harorat keskin o‘zgarmasligi muhim. Ketma-ket daqiqalardan iborat davr (l-daqiqadan r-daqiqagacha, l ≤ r) barqaror deyiladi, agar bu davrdagi eng yuqori va eng past harorat ayirmasi K dan oshmasa:

max(tₗ, …, tᵣ) − min(tₗ, …, tᵣ) ≤ K.

To‘garak rahbari Nodira opa barqaror davrlar nechta ekanini bilmoqchi. Bitta daqiqadan iborat davr ham hisobga kiradi; ikki davr boshi yoki oxiri bilan farq qilsa, ular har xil hisoblanadi.

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va K.

Ikkinchi qatorda N ta butun son t₁, t₂, …, t_N — o‘lchangan haroratlar.

Chiqish ma’lumotlari

Bitta butun son — barqaror davrlar soni.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 0 ≤ K ≤ 2·10⁹
• −10⁹ ≤ tᵢ ≤ 10⁹
• Javob 32 bitli songa sig‘masligi mumkin: C++ da long long ishlating.

1-misol: bitta daqiqalik davrlar — 5 ta. Ikki daqiqalik: [1, 2] (5 − 3 = 2), [2, 3] (1), [4, 5] (1) barqaror, [3, 4] esa yo‘q (7 − 4 = 3). Uch daqiqalik: faqat [1, 3]. Uzunroq barqaror davr yo‘q. Jami 5 + 3 + 1 = 9.

2-misol: K = 0 — davrdagi barcha harorat teng bo‘lishi kerak: [1], [2], [3] va [1, 2].