დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
ბესი მოგზაურობს საინტერესო ლანდშაფტის მქონე გზაზე. თუ ამ გზას წარმოვიდგენთ რიცხვით ღერძად, ბესი მოგზაურობას იწყებს x=0 წერტილში. ღერძზე მდებარეობს N(1<=N<=50,000) "წარმტაცი ადგილი", რომლებიც განლაგებულნი არიან წერტილებში X(1)..X(N) (-10,000<=X(i)<=10,000). ბესის სურს მოასწროს რაც შეიძლება ბევრი „წარმტაცი ადგილის“ ნახვა მზის ჩასვლამდე, სანამდეც დარჩენილია T(1<=T<=1,000,000,000) წუთი. მზის ჩასვლის მომენტში მოძრაობა წყდება. ბესის მანძილის ერთეულის გასავლელად დროის 1 ერთეული სჭირდება.
ბესი „წარმტაც ადგილებს“ მოინახულებს გარკვეული თანმიმდევრობით. კერძოდ, ის ყოველთვის მიემართება იმ ადგილისაკენ, რომელიც მას ჯერ არ უნახავს და რომელიც ყველაზე ახლოსაა მის საწყის წერტილთან (x=0). დაეხმარეთ ბესის, რათა მან დაადგინოს, რამდენი „წარმტაცი ადგილის“ ნახვა შეუძლია მზის ჩასვლამდე. „წარმტაცი ადგილების“ არცერთი წყვილი არ მდებარეობს ერთნაირ მანძილზე საწყისი წერტილიდან.
შესატანი მონაცემები: პირველ სტრიქონში წერია ორი მთელი რიცხვი T და N. მომდევნო N სტრიქონიდან თითოეულში წერია თითო მთელი რიცხვი: X(i).
გამოსატანი მონაცემები: ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი რიცხვი - რამდენი „წარმტაცი ადგილის“ ნახვა შეუძლია ბესის მზის ჩასვლამდე.
შესატანი მონაცემები
25 5 10 -3 8 -7 1 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება
ბესი მოინახულებს „წარმტაც ადგილებს“ შემდეგი თანმიმდევრობით: 1, -3, -7, 8 და ამაზე მას დაეხარჯება 24 წუთი. ის ვეღარ მოასწრებს მე-10 პოზიციაში მისვლას, რადგან ამისთვის მას 26 წუთი დასჭირდებოდა.