Muallif: __thecrash__
F. Tog' sayohati
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Sardor do'stlari bilan Chimyon tog'lariga piyoda sayohatga otlandi. Yo'nalish bo'ylab ketma-ket \(n\) ta to'xtash nuqtasi bor, \(i\)-nuqtaning dengiz sathidan balandligi \(a_i\) metr.
Sayohat bir necha kunga bo'linadi. Har kuni guruh qandaydir \(l\)-nuqtadan yo'lga chiqadi va \(r\)-nuqtada (\(l \le r\)) tunab qoladi; ertasi kuni esa \((r+1)\)-nuqtadan yo'lga chiqadi. Birinchi kun \(1\)-nuqtadan boshlanadi, oxirgi kun esa aynan \(n\)-nuqtada tugashi kerak. Shunday qilib, har bir nuqta roppa-rosa bitta kunga tegishli bo'ladi.
Sardorning qat'iy qoidasi bor: kunlik yo'l "yoqimli" bo'lishi kerak. Ya'ni:
- kun boshlanadigan \(l\)-nuqta shu kungi yo'ldagi eng past nuqta bo'lishi kerak: \(a_l \le a_i\), barcha \(l \le i \le r\) uchun;
- kun tugaydigan \(r\)-nuqta shu kungi yo'ldagi eng baland nuqta bo'lishi kerak: \(a_r \ge a_i\), barcha \(l \le i \le r\) uchun.
Masalan, balandliklari \([1, 3, 2, 4]\) va \([1, 2, 1, 2]\) bo'lgan kunlik yo'llar yoqimli, \([1, 3, 2]\) esa yoqimli emas, chunki kun eng baland nuqtada tugamayapti. Bitta nuqtadan iborat kunlik yo'l har doim yoqimli.
Do'stlar tezroq uyga qaytmoqchi. Butun yo'nalishni eng kamida nechta yoqimli kunga bo'lish mumkinligini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 300\,000\)) — to'xtash nuqtalari soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — nuqtalarning balandliklari.
Chiquvchi ma'lumotlar
Bitta son — sayohat uchun kerak bo'ladigan eng kam kunlar soni.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
6 2 3 1 1 5 1 |
3 |
2 |
5 5 4 3 2 1 |
5 |