Masala #1022
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 ≤ Ai ≤ 106 )
Dehqon ota sug'orishni ixtiyoriy Ai ariqdan boshlaydi. Ariqni kesib suv olib o'tish mumkin emas. Faqatgina A i +1 ≤ A i 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.
Birinchi qatorda N ( 1 ≤ N ≤ 2*105 ) butun son massiv uzunligi va keyingi qatorda N ta elementdan iborat A massiv beriladi.
Yagona qatorda dehqon ota maksimum nechta ariqni sug'ora olishini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
8 2 3 2 2 2 4 4 5 |
6 |
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.
Telegram kanalimizga obuna bo'ling