Tin rằng những cô bò vui vẻ sẽ cho nhiều sữa hơn, bác nông dân John đã lắp một quả cầu disco khổng lồ trong chuồng và dự định dạy đàn bò của mình khiêu vũ!

Sau khi tìm hiểu các điệu nhảy phổ biến của loài bò, bác nông dân John quyết định dạy đàn bò điệu “Bovine Shuffle”. Điệu Bovine Shuffle bắt đầu với \(N\) cô bò (\(1 \leq N \leq 100{,}000\)) xếp thành một hàng theo một thứ tự nào đó, rồi thực hiện liên tiếp nhiều lần “xáo trộn”, mỗi lần có thể sắp xếp lại đàn bò. Để đàn bò dễ xác định vị trí của mình hơn, bác nông dân John đánh dấu các vị trí trong hàng từ \(1 \ldots N\): cô bò đầu hàng đứng ở vị trí \(1\), cô tiếp theo ở vị trí \(2\), và cứ thế cho đến vị trí \(N\).

Một lần xáo trộn được mô tả bởi \(N\) số \(a_1 \ldots a_N\), trong đó một cô bò ở vị trí \(i\) sẽ di chuyển đến vị trí \(a_i\) trong lần xáo trộn đó (vì vậy mỗi \(a_i\) nằm trong khoảng \(1 \ldots N\)). Mọi cô bò đều di chuyển đến vị trí mới trong lần xáo trộn. Không may, các giá trị \(a_i\) không nhất thiết phải khác nhau, nên nhiều cô bò có thể cố di chuyển đến cùng một vị trí trong một lần xáo trộn; sau đó, chúng sẽ di chuyển cùng nhau trong tất cả các lần xáo trộn còn lại.

Bác nông dân John nhận thấy rằng có một số vị trí trong hàng luôn chứa bò, bất kể thực hiện bao nhiêu lần xáo trộn. Hãy giúp bác đếm số vị trí như vậy.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số lượng bò. Dòng tiếp theo chứa \(N\) số nguyên \(a_1 \ldots a_N\).

Dữ liệu ra

In ra số vị trí sẽ luôn chứa bò, bất kể thực hiện bao nhiêu lần xáo trộn.

Ví dụ

4
3 2 1 3

3

Nguồn

USACO 2017 December Contest, Silver — The Bovine Shuffle

Tác giả bài toán: Brian Dean.