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

1

6
2 3 1 1 5 1

3

2

5
5 4 3 2 1

5