Trên lục địa Runeterra, tồn tại một vòng tròn gồm \(n\) phiến đá có ma thuật mang trong mình sức mạnh kỳ bí. Mỗi phiến đá được khắc một con số ma thuật - chỉ dẫn bí ẩn về "phiến đá tiếp theo" mà nó sẽ liên kết.

Người ta truyền tai nhau rằng, nếu xếp những phiến đá này theo thứ tự từ \(1\) đến \(n\) và áp dụng "Phép Biến Đổi Cổ Ngữ", con số ma thuật trên toàn bộ phiến đá sẽ đồng loạt biến đổi theo quy luật. Số trên phiến đá thứ \(i\) sẽ biến đổi thành số trên phiến đá thứ \(r(i)\). Dãy \(r\) tượng trưng cho "Phép Biến Đổi" trên, cho trước và không thay đổi (\(r\) khác với con số trên phiến đá).

Tuy nhiên, các hiền nhân cổ đại nhận ra rằng, nếu lặp đi lặp lại nghi thức này đủ nhiều lần, chúng sớm hay muộn sẽ rơi vào một trạng thái bất biến. Trạng thái này là một trạng thái lặp vô tận, nếu tiếp tục thực hiện thêm "Phép Biến Đổi" thì các con số vẫn không thay đổi (tính chất tuần hoàn).

Các học giả vĩ đại của Piltover đang tìm cách khám phá thời gian ngắn nhất để toàn bộ hệ thống phiến đá này đạt đến trạng thái ổn định. Nhiệm vụ của bạn là giải mã bí ẩn này và tìm ra số bước tối thiểu cần thiết để đi đến trạng thái bất biến nêu trên.

Input

• Dòng đầu tiên chứa \(n\) - số lượng phiến đá \((1 \leq n \leq 1000)\)
• Dòng thứ hai chứa \(n\) số \(r_1, r_2, r_3, \ldots, r_n(1 \leq r_i \leq n)\) - quy luật biến đổi, cũng như giá trị ban đầu của số trên phiến đá.

Output

• Một số nguyên duy nhất - số bước tối thiểu để tất cả các phiến đá đạt đến trạng thái ổn định.
• Dữ liệu đảm bảo kết quả chứa vừa trong kiểu số nguyên 64-bit, ví dụ như long long của C++

Example

3
2 3 1

3

4
2 2 3 3

1

Scoring

• Subtask 1 (10% số điểm): \(n = 1\)
• Subtask 2 (15% số điểm): \(r_i = (i + 1) \bmod n + 1\)
• Subtask 3 (20% số điểm): \(r\) là hoán vị
• Subtask 4 (25% số điểm): \(|i - r_i| \leq 1\)
• Subtask 5 (30% số điểm): Không có ràng buộc thêm