პორტი

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

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

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

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

წყარო: COCI, 2010/11, #5


მირკო ცხოვრობს პორტის მახლობლად და ახლაც მკაფიოდ ახსოვს ის დღე, როდესაც ნაპირთან  თავი მოიყარა ყველა იმ N (1<=N<=5000) გემმა, რომელიც ოდესმე მაინც შემოსულა პორტში. ეს დღე მირკომ აღნიშნა ინდექსით 1 და მას შემდეგ დაიწყო ყველა იმ დღის მონიშვნა, როდესაც პორტში ერთი გემი მაინც შემოვიდა. გარდა ამისა, მირკომ შენიშნა, რომ თითოეული გემი პორტში შემოდის გარკვეული პერიოდულობით. მაგალითად, თუ ეს პერიოდულობა 3 დღეა, მაშინ გემი პორტში შემოვა 1, 4, 7, და ა.შ. დღეებში.

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

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი - იმ დღეების რაოდენობა, როცა მირკომ მონიშნა პორტში შემოსული გემები. მომდევნო N სტრიქონიდან თითოეულში მოცემულია იმ დღის ნომერი, როცა მირკომ პორტში შესული გემები მონიშნა. პირველი რიცხვი ყოველთვის 1-ის ტოლია. ბოლო რიცხვი არ აღემატება 109-ს.

გამოსატანი მონაცემები: ერთადერთ სტრიქონში ერთი მთელი რიცხვი - პორტში შემოსული გემების მინიმალური რაოდენობა.

 




მაგალითები

შესატანი მონაცემები
3 1 3 4 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
შესატანი მონაცემები
5 1 7 10 13 19 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
შესატანი მონაცემები
3 1 500000000 999999999 დაკოპირება
გამოსატანი მონაცემები
1 დაკოპირება