ჯარისკაცები

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

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

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

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

წყარო: GEOI, 2010, რეგიონული, X კლასი


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

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

შესატანი მონაცემები:  პირველ სტრიქონში მოცემულია ერთი მთელი დადებითი n რიცხვი (2 ≤ n ≤ 1000) – ჯარისკაცთა რაოდენობა. მეორე სტრიქონი შეიცავს თითო ჰარით გამოყოფილ n რაოდენობის ნამდვილ რიცხვს [0.5; 2.5] ინტერვალიდან (ათობითი წერტილის შემდეგ არაუმეტეს 5 ციფრის სიზუსტით).  k-ური რიცხვი ამ სტრიქონში გამოსახავს იმ ჯარისკაცის სიმაღლეს, რომლის რიგითი ნომერიც თავდაპირველ განლაგებაში k-ს ტოლია (1 ≤ k ≤ n). 

გამოსატანი მონაცემები:  ერთადერთ სტრიქონში უნდა ჩაიწეროს ჯარისკაცთა საძიებელი მინიმალური რაოდენობა.

 




მაგალითები

შესატანი მონაცემები
8 1.86 1.86 1.30621 2 1.4 1 1.97 2.2 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება

შენიშვნა

განმარტება: ახალი რიგი ფორმირებულია ჯარისკაცებით, რომელთა ნომრებია:    2, 4, 5, 6 და რომელთა სიმაღლეებია: 1.86 2 1.4 1.

ჯარისკაცი, რომლის ნომერია 2, ხედავს რიგის ერთ ბოლოს;

ჯარისკაცი, რომლის ნომერია 4, ხედავს რიგის ორივე ბოლოს;

ჯარისკაცები, რომელთა ნომრებია 5 და 6, ხედავენ ასევე რიგის ერთ ბოლოს;