Masala #0452

Xotira 256 MB Vaqt 2000 ms Qiyinchiligi 60 %
4.2 (Baholar 5)
14

  

Ajoyib ketma-ketliklar

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

Sizga uzunligi nn ga teng aa 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 nn kiritiladi (1n200000)(1 \leq n \leq 200000)
Ikkinchi qatorda a1,a2,...,ana_1, a_2, ..., a_n kiritiladi (1ai109)(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][4,1,5], [3], [9,5,7,8,9] ko’rinishida bo’lish mumkin.
Ikkinchi misolda massivni [2,2],[2][2, 2], [2] ko’rinishida bo’lish mumkin.
Uchinchi misolda butun massiv ajoyib hisoblanadi, demak minimal javob 1.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin