საჩუქრები

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

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

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

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


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

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

შემავალი მონაცემების ფორმატი:
* სტრიქონი 1: ერთი მთელი N.
* სტრიქონი 2..N+1: i-ური ხაზი შეიცავს ერთ მთელს next_i.

გამომავალი მონაცემების ფორმატი:
* სტრიქონები 1..N: i-ხაზი შეიცავს ერთ მთელს - გაჩერებამდე რამდენ პრიზს მოაგროვებს i-ური სტუდენტი.




მაგალითები

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

შენიშვნა

განმარტება: მოცემულია ოთხი ყუთი.

* ყუთი 1-ის შემდეგ სანახავია ყუთი 1
* ყუთი 2-ის შემდეგ სანახავია ყუთი 3
* ყუთი 3-ის შემდეგ სანახავია ყუთი 2
* ყუთი 4-ის შემდეგ სანახავია ყუთი 3

 

ძროხა 1: მიაკითხავს 1 ყუთს, შემდეგ ისე 1 ყუთს. ჯამში მოაგროვებს 1 პრიზს.
ძროხა 2: მიაკითხავს 2, შემდეგ 3, შემდეგ 2 ყუთებს. ჯამში მოაგროვებს 2 პრიზს.
ძროხა 3: მიაკითხავს 3, შემდეგ 2, შემდეგ 3. ჯამში მოაგროვებს 2 პრიზს.
ძროხა 4: მიაკითხავს 4, შემდეგ 3, შემდეგ 2, შემდეგ 3. ჯამში მოაგროვებს 3 პრიზს.