ჭის ამოთხრა

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

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

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

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

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


 

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

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

 

შემომავალი ინფორმაცია

პირველი ხაზი სტანდარტული ინფუთისა არის ორი დადებითი ინტეჯერი n და m (1 ≤ n ≤ 1 000 000, 1 ≤ m ≤ 1018), რომლებიც გამოყოფილია ერთი ცალი ჰარით (სფეისით). მეორე ხაზი შეიცავს n-ცალ დადებით ინტეჯერს X1, X2, …., Xn (1 ≤ Xi ≤ 109), რომლებიც გამოყოფილია ასევე ერთი ჰარით.

ბაითაზარს აქვს გამძლეობა, რომ გააკეთოს m ნიჩაბის მოძრაობა. რიცხვები X1, X2, …., Xn წარმოადგენენ ტოპოგრაფიულ აღწერას მშრალი მდინარის კალაპოტის, რომელიც გამოდგება ჭის ამოსათხრელად. ეს რიცხვები წარმოადგენენ ქვიშის ფენის სისქეს, მიმდევრობით ადგილებში, ყოველ მეტრზე კალაპოტის გასწვრივ. ერთი ნიჩაბის მოძრაობით, ბაითაზარს შეუძლია მონიშნოს საკმარისი ქვიშა, რომ შეამციროს Xi-ის ერთ ერთი რიცხვი 1-ით. თუ რომელიმე Xi -ის რომელიმე რიცხვი, მაგალითად Xk შემცირდება 0-მდე, ეს ნიშნავს იმას, რომ ბაითაზარმა წყლამდე ჩააღწია. წყლამდე ჩასვლასთან ერთად, ერთ წერტილში მაინც, ბაითაზარს უნდა, რომ მოცემული რიცხვი Z, საბოლოოდ ახასიათებდეს ფერდობის დახრას და იყოს რაც შეიძლება პატარა.

                                                                         z=max|xi-xi-1|

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

დამატებითი ინფორმაცია: თუ თქვენი პროგრამა ტესტის 35%-ს მაინც თუ იღებს, ესეიგი n < 10 000.

 

გამომავალი ინფორმაცია

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

 

 




მაგალითები

შესატანი მონაცემები
16 15 8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5 დაკოპირება
გამოსატანი მონაცემები
1 2 დაკოპირება

შენიშვნა

თარგმანი შესრულებულია ლაშა ანდღულაძის მიერ.