Васе скучно, и он от нечего делать взял n кубиков, пронумерованных числами от 1 до n, перемешал их и расставил в случайном порядке. После этого он несколько раз перемешал кубики и расставил их в том порядке, в котором они оказались. После каждого перемешивания он смотрел, не получилась ли та же самая перестановка, что и перестановка, получившаяся после первого перемешивания. Но кубиков было много, искомая перестановка всё никак не получалась, и Васе опять стало скучно.

Но Вася подумал и решил получить искомую перестановку другим способом. Он расставил кубики по порядку от 1 до n и решил выбрать часть кубиков, перемешать их и вернуть на те же места, но, возможно, в другом порядке. Он решил повторять эти действия до тех пор, пока не получится перестановка, которую он запомнил в самом начале, но перед этим ему хочется узнать, через какое время, в среднем, он сможет этого добиться? Вася хочет получить эту перестановку как можно быстрее и выбирает кубики, которые он будет перемешивать, соответственно.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 1000). Вторая строка содержит n целых чисел от 1 до n - перестановка, которую хочет получить Вася.

Выходные данные

Выведите одно число - среднее количество перемешиваний, после которых Вася получит искомую перестановку.