Masala #0452

Xotira 256 MB Vaqt 2000 ms
14

Ajoyib ketma-ketliklar

Uzungligi \(m\) ga teng \(b_1,b_2,...,b_m\) ketma-ketlik ajoyib bo’lishi uchun, uning ikki chetidagi elementlari qolgan \(m-2\) ta elementdan qat’iy katta bo’lishi kerak. Boshqacha qilib aytganda \(\min (b_1,b_m) > \max (b_2,b_3,...,b_{m-1})\) shart bajarilishi kerak. E’tibor bering, \(m \leq 2\) bo’lsa ketma-ketlik ajoyib hisoblanadi.

Sizga uzunligi \(n\) ga teng \(a\) massiv berilgan. Sizning vazifangiz massivni bir nechta oraliqlarga bo’lish, bunda har bir element aynan bitta oraliqqa tegishli bo’ladi va har bir oraliqdagi elementlar ajoyib ketma-ketlikni tashkil qiladi. Yuqoridagi shartlar bajarilishi uchun minimal oraliqlar sonini toping.


Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) kiritiladi \((1 \leq n \leq 200000)\)
Ikkinchi qatorda \(a_1, a_2, ..., a_n\) kiritiladi \((1 \leq a_i \leq 10^9)\).


Chiquvchi ma'lumotlar:

Bitta qatorda minimal oraliqlar sonini chiqaring.


Misollar
# input.txt output.txt
1
9
4 1 5 3 9 5 7 8 9
3
2
3
2 2 2
2
3
3
3 1 2
1
Izoh:

Birinchi misolda massivni \([4,1,5], [3], [9,5,7,8,9]\) ko’rinishida bo’lish mumkin.
Ikkinchi misolda massivni \([2, 2], [2]\) ko’rinishida bo’lish mumkin.
Uchinchi misolda butun massiv ajoyib hisoblanadi, demak minimal javob 1.