მაფია

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

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

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

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

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


 

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

 

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

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

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

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

 შესატანი მონაცემები:  პირველი სტრიქონი შეიცავს მაფიოზების რაოდენობას n(1 <= n <= 106).

მეორე სტრიქონი შეიცავს ერთმანეთისგან ერთი სფეისით დაშორებულ მთელ რიცხვს (1 <= Sk <= n) სადაც   Sk  არის იმ მაფიოზის ნომერი, რომელსაც უმიზნებს   k  ინდექსზე მყოფი მაფიოზი. Sk  შეიძლება იყოს k-ს ტოლიც.

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

 

 




მაგალითები

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