Masala A
Birinchi ishonch
Bir yil oldin kanalga ilk xabarlar joylanayotgan paytda hali hech kim katta sarlavhalar haqida o'ylamagan edi. Avval bitta o'quvchi viloyatda yaxshi natija ko'rsatdi, keyin yana bittasi. Vaqt o'tib, saralash bosqichlari, respublika natijalari va xalqaro medallar ham shu kundalik yozuvlar qatoriga qo'shildi.
Ismoilmirzo har bir natijani oddiy son bilan belgilab borgan. \(i\)-xabarga yozilgan son \(a_i\) bo'lsin. Agar \(a_i\) o'zidan oldingi barcha sonlardan qat'iy katta bo'lsa, \(i\)-xabar yangi bosqich deyiladi. Xususan, birinchi xabar har doim yangi bosqich hisoblanadi.
Lekin ishonch bitta katta sakrashdan emas, ketma-ket ko'rinib turgan o'sishdan paydo bo'ladi. Shuning uchun yangi bosqichlarning faqat ayrimlari ishonch belgisi deb sanaladi:
- birinchi yangi bosqich har doim ishonch belgisi;
- keyingi har bir yangi bosqich \(a_i\) faqat \(a_i - q \le k\) bo'lsa ishonch belgisi sanaladi. Bu yerda \(q\) - undan oldingi eng so'nggi yangi bosqichdagi son.
E'tibor bering: agar yangi bosqich \(a_i - q > k\) bo'lgani uchun ishonch belgisi sanalmasa ham, u yangi bosqichligicha qoladi; keyingi taqqoslashlarda \(q\) o'rnini aynan u egallaydi.
Berilgan xabarlar ichida nechta ishonch belgisi borligini toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 1 \le k \le 10^9)\).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Ishonch belgilarining sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
6 5 2 4 10 12 16 15 |
4 |
| 2 |
4 3 10 9 15 16 |
2 |
| 3 |
1 100 7 |
1 |
Birinchi namunada yangi bosqichlar \(2\), \(4\), \(10\), \(12\), \(16\). \(2\) birinchi yangi bosqich bo'lgani uchun sanaladi. \(4-2=2\), \(12-10=2\) va \(16-12=4\) qiymatlarining har biri \(k=5\) dan oshmaydi, demak ular ishonch belgisi. \(10-4=6 > 5\) bo'lgani uchun \(10\) ishonch belgisi emas, lekin keyingi taqqoslash aynan \(10\) bilan olib boriladi.
Ikkinchi namunada \(10\) birinchi yangi bosqich. \(15-10=5 > 3\) bo'lgani uchun \(15\) sanalmaydi, lekin yangi bosqich bo'lib qoladi. \(16-15=1 \le 3\), shuning uchun \(16\) ishonch belgisi. Jami \(2\) ta.
Uchinchi namunada bitta xabar bor va u birinchi yangi bosqich sifatida ishonch belgisi hisoblanadi.
Telegram kanalimizga obuna bo'ling