Có ~ n ~ đứa trẻ, mỗi ngày một đứa trẻ đọc một quyển sách khác nhau. Kết thúc một ngày, đứa trẻ thứ ~ i ~ sẽ đưa quyển sách của mình cho đứa trẻ thứ ~ p_i ~, nếu ~ i=p_i ~ thì xem như đứa trẻ đó tự đưa cho chính mình. Biết rằng tất cả các giá trị ~ p_i ~ là đôi một phân biệt từ 1 đến ~ n ~, hay nói cách khác ~ p_1,p_2,…,p_n ~ là một hoán vị của ~ 1,2,3,…,n ~

Ví dụ ~ n=6 ~ và ~ p={4,6,1,3,5,2} ~ khi kết thúc ngày đầu tiên quyển sách của đứa trẻ thứ nhất sẽ đưa cho đứa trẻ thứ 4, quyển sách của đứa trẻ thứ 2 sẽ đưa cho đứa trẻ thứ 6, quyển sách của đứa trẻ thứ 3 sẽ đưa cho đứa trẻ thứ 1,… Kết thúc ngày thứ 2, quyển sách của đứa trẻ thứ nhất sẽ chuyển qua đứa trẻ thứ 3, quyển sách của đứa trẻ thứ 2 sẽ chuyển qua đứa trẻ thứ 2.

Hãy xác định số ngày ít nhất để quyển sách của đứa trẻ thứ ~ i ~ quay lại chính đứa trẻ thứ ~ i (i=1…n) ~

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên ~ n ~ cho biết số lượng đứa trẻ
• Dòng thứ 2 ghi n số nguyên ~ p_1,p_2,…,p_n (1≤p_i≤n) ~ trong đó số ~ p_i ~ cho biết đứa trẻ thứ ~ p_i ~ sẽ nhận quyển sách của đứa trẻ thứ ~ i ~.

Kết quả

Đưa ra dãy số nguyên ~ a_i,a_2,…,a_n ~ trong đó ~ a_i ~ cho biết số ngày ít nhất để đứa trẻ thứ ~ i ~ nhận lại quyển sách ban đầu của mình.

Ràng buộc

• Sub1: 50% số test có ~1≤n≤2000 ~
• Sub2: 50% số test có ~ 1≤n≤10^6 ~

Ví dụ:

Input 1

6
4 6 2 1 5 3 

Output 1

2 3 3 2 1 3