გოჭუნია ყულაბები

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

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

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

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

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


 

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

დაწერეთ პროგრამა რომელიც:

  •          წაიკითხავს ყულაბების რაოდენობას და შესაბამისი გასაღებების განლაგებას;
  •          დაითვლის მინიმუმ რამდენი ყულაბის გატეხვაა საჭირო ყველას გასახსნელად (გატეხვა ასევე გახსნად ითვლება);
  •          გამოიტანს შესაბამის პასუხს.

შესავალი მონაცემები: პირველ ხაზში შემოდის დადებითი მთელი რიცხვი (1 <= N <= 1 000 000), ყულაბების რაოდენობა. ყულაბები და გასაღებები თითეული ყულაბისთვის გადათვლილია 1-იდან N-ის ჩათვლით. შემდეგ N ხაზში წერია 1 დადებითი მთელი რიცხვი K (1 <= K <= N), ყულაბის ნომერი რომელშიც დევს Ni-იური ყულაბის გასაღები.

გამოსატანი მონაცემები: გამოიტანეთ ზუსტად ერთი რიცხვი: მინიმუმ რამდენი ყულაბის გატეხვაა საჭირო, რომ ყველა ყულაბა გაიხსნას (ან გატყდეს თუ საჭიროა).

 




მაგალითები

შესატანი მონაცემები
4 2 1 2 4 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

რიცხვი 4 არის ყულაბების რაოდენობა. შემდეგ წერია ყულაბების ნომრები, რომლებშიც კონკრეტული ინდექსის ყულაბის გასაღები დევს, მაგ. 1-ლი ყულაბის გასაღები დევს მე-2 ყულაბაში.

შესაბამისად მე-2 ყულაბის გატეხვით გაიხსნება 1-ლი ყულაბაც, მე-2 ყულაბაც და მე-3 ყულაბაც. მე-4 ყულაბაში დევს თავისი გასაღები, ამიტომ მისი გატეხვაც აუცილებელია. გამოსატანი პასუხი: 2.

 

სერგო პოლიაკოვის თარგმანი.