Masala #1022

Xotira 64 MB Vaqt 1000 ms
14

Dehqonning dangasa o'g'li

Dehqon ota o'z o'g'liga ariqlarni olib qo'yish ishini yukladi. Lekin dehqonning o'gli dangasa va erinchoq edi. U ariqlarni har xil uzunliklarda oldi. Endilikda suv kelib qolganligi bois dehqon ota ariqlarni to'g'rilay olmaydi. Dehqon ota o'g'li olgan ariqlarning maksimum nechtasini sug'ora olishi mumkinligini aniqlang.

Sizga N dangasa o'g'li olgan ariqlar soni va N ta elementdan iborat A massiv beriladi. Ai : i (1 ≤ i ≤ N ) - ariqning uzunligini bildiradi.(1 ≤ A≤ 106 )  

Dehqon ota sug'orishni ixtiyoriy Ai ariqdan boshlaydi. Ariqni kesib suv olib o'tish mumkin emas. Faqatgina A i +1 ≤ A yoki A i -1 ≤ A i bo'lganda qo'shni ariqqa suv olib o'tishi mumkin.

Agar N = 8 va A = { 2, 1, 3, 4, 5, 3, 1, 6} ;

Barcha holatlar rasmda tasvirlangan.

Dehqon ota 5 - ariqdan boshlasa maksimum ariqlarni sug'ora oladi (rasmga qarang ). Ya'ni 2-,3-,4-,5-,6-,7 - ariqlarni sug'oradi. Bu holat uchun javob shuning uchun 6.

 


Kiruvchi ma'lumotlar:

Birinchi qatorda N ( 1 ≤ N ≤ 2*105 ) butun son massiv uzunligi va keyingi qatorda N ta elementdan iborat A massiv beriladi. 


Chiquvchi ma'lumotlar:

Yagona qatorda dehqon ota maksimum nechta ariqni sug'ora olishini chiqaring.


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

Birinchi testda dehqon ota sug'orishni  8 ( A 8 = 5 ) - ariqdan boshlaydi va 2 ( A 2 = 3 ) - ariqgacha sug'ora oladi. Sug'ora oladigan ariqlari - 3, 4, 5, 6, 7, 8 ( ya'ni ularning uzunliklari mos ravishda 2, 2, 2, 4, 4, 5 ) ariqlaridir.

Dehqon ota maksimum 6 ta ariqni sug'ora oladi.