Masala D

Shohruh quyidagi massivni chiroyli deb ataydi:

• massivning uzunligi kamida 2 ga teng;
• massiv quyidagi ikki holatning biriga mos tushadi:
  • massivdagi har bir element (birinchi elementdan tashqari) o'zidan oldingi elementdan katta emas; (non-increasing)
  • massivdagi har bir element (birinchi elementdan tashqari) o'zidan oldingi elementdan kichik emas; (non-decreasing)

$N$ uzunlikdagi butun sonlardan tashkil topgan $A$ massivi berilgan. Shohruh ushbu massivni bir nechta subsequence* larga ajratishi kerak:

• Har bir subsequnce chiroyli bo'lishi kerak;
• $A$ ning har bir elementi aynan 1 ta subsequence ichida bo'lishi kerak;

Shohruh eng kamida nechta subsequence yaratishi kerakligini aniqlang.

Subsequence — bu massivdan ba’zi elementlarni (ehtimol 0 ta) olib tashlab, qolganlarini tartibini o‘zgartirmasdan tuzilgan yangi massivdir.

Birinchi qatorda bitta butun son $N \ (1 \le N \le 25)$ - massiv uzunligi kiritiladi.

Keyingi $N$ ta qatorda $A_i \ (1 \le A_i \le 100)$ - massiv elementlari beriladi.

Barcha shartlarga javob berish uchun yaratilishi kerak bo'lgan minimal subsequence lar sonini chop eting. Agar shartni bajarish imkonsiz bo'lsa 0 ni chop eting.