პილოტები

დროის ლიმიტი: 5 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 17, ეტაპი 3


ბაიტანის სასწავლო ცენტრში პილოტები ემზადებიან ისეთი მისიების შესასრულებლად, რომლებიც განსაკუთრებულ სიზუსტესა და ოსტატობას მოითხოვს.  ფრენის წარმატების საზომს წარმოადგენს ყველაზე გრძელი ფრენის შესრულება  განსაზღვრულ ტრაექტორიაზე გადაჭარბებული გადახრის გარეშე ანუ აღებული   კურსის შენარჩუნებით.  ეს მათთვის რთული ამოცანაა, რადგან სიმულატორი იმდენად მგრძნობიარეა,  რომ ის აღიქვამს საკონტროლო მოწყობილობის უმცირესს მოძრაობებსაც კი. ის  ინახავს ე.წ. რხევის პარამეტრს.  

 თითოეული სასწავლო ექსპერიმენტის წინ მფრინავებს აქვთ მითითებული t  დასაშვები ცდომილების დონე. მათი მიზანია, რაც შეიძლება დიდი ხნის         განმავლობაში შექმნან ფრენის ისეთი ფრაგმენტი, რომელშიც გადახრის თითოეული მაჩვენებლის აბსოლუტური სხვაობა ამავე ფრაგმენტში არსებულ  სხვა ნებირმიერ მაჩვენებელთან არ აღემატება t დასაშვები ცდომილების დონეს. სხვა სიტყვებით რომ ვთქვათ, ფრენის ფრაგმენტი i-ური მომენტიდან j-ურ      მომენტამდე მიგვაჩნია t დასაშვები ცდომილების ფარგლებში, თუ გადახრის  მაჩვენებელი დაწყებული i-იური საზომიდან, დამთავრებული j-ურით,      წარმოადგენს ისეთ a(i). . . . .a(j) თანმიმდევრობას რომ ამ თანმიმდევრობიდან  ნებისმიერი a(k), a(l) ისთვის სრულდება პირობა |a(k) - a(l)| <= t. 

 ჩვენი ამოცანაა, დავწეროთ პროგრამა, რომლითაც განვსაზღვრავთ, სტრინგად   წარმოდგენილი რხევის მაჩვენებლების მიმდევრობაში, მოცემული დასაშვები      ცდომილების დონიდან გამომდინარე ამ სტრინგის ყველაზე გრძელი ფრაგმენტის სიგრძეს.   

 შემომავალი ინფორმაცია: პირველი ხაზი შეიცავს ერთი სფეისით გამოყოფილ ორ რიცხვს ​t​ და​ n  (0 ​≤​ ​t​ ​≤​ 2 000 000 000, 1 ​≤​ ​n​ ​≤​ 3 000 000) ეს რიცხვები შესაბამისად წარმოადგენენ დასაშვები ცდომილების დონესა და   ფრენისას გაკეთებული გადახრების გაზომვების რაოდენობას. მეორე ხაზი შეიცავს სფეისით გამოყოფილ რიცხვებს, რომლებიც გამოხატავენ   თითოეული გაზომვისას მიღებულ გადახრის მაჩვენებლებს, რომელთაგანაც      თითოელი მოთავსებულია 1-დან 2 000 000 000-მდე შუალედში. 

 გამომავალი ინფორმაცია: პროგრამამ უნდა დააბრუნოს რიცხვი რომელიც გამოხატავს ფრენის ფრაგმენტის მაქსიმალურ სიგრძეს, რომელშიც დასაშვები ცდომილების დონე არ დარღვეულა. 

 

 

 




მაგალითები

შესატანი მონაცემები
3 9 5 1 3 5 8 6 6 9 10 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება

შენიშვნა

განმარტება​: ზემოთ განსაზღვრულ მაგალითში ჩვენ გვაქვს ორი უგრძესი ფრაგმენტი,  რომელთაგან ორივეს აქვს სიგრძე 4, ესენია : 5, 8, 6, 6 და 8, 6, 6, 9