eolymp
bolt
Try our new interface for solving problems
Problems

Island of Misfortune

Island of Misfortune

Time limit 1 second
Memory limit 64 MiB

"All covered with herbs,

Absolutely all,

sland in an ocean of bad luck there..."

Strange people live on the island of bad luck, and each of them every morning, gives his unique shoes to his best and only friend. Different people have different best friends. After a certain number of days they are finally happy to learn that all footwear returned to their original owners. But they have already managed to forget how many days have passed from the previous same joyous day, so they ask you, how very clever programmer to find after a minimum number of days of their holiday begins.

Input data

The input data contain several test cases. Each test case contains an integer N (0 < N < 6001), indicating the number of people living on the island. The next line of each test contains N integers (from 1 to N), indicating a better one of each i-th person living on the island.

Output data

For each test case in a separate line output the smallest possible number of days between holidays.

Examples

Input example #1
2
2 1
5
3 2 1 5 4
Output example #1
2
2