Masala #1022

Xotira 64 MB Vaqt 1000 ms Qiyinchiligi 20 %

#Massivlar

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. A_i: i (1 ≤ i ≤ N ) - ariqning uzunligini bildiradi.(1 ≤ A_i≤ 10⁶ )

Dehqon ota sug'orishni ixtiyoriy A_i ariqdan boshlaydi. Ariqni kesib suv olib o'tish mumkin emas. Faqatgina A_{i +1}≤ A _iyoki 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*10⁵ ) 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.

Telegram Facebook

Yechimini yuborish

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