e-olymp
Задачи

Случайное совпадение

Случайное совпадение

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

Формат входного файла

Первая строка входного файла содержит целое число N.

1 N1000

Вторая строка содержит Nцелых чисел от 1 до N— перестановка, которую хочет получить Вася.

Формат выходного файла

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

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные
Sample 1
3
2 1 3
Sample 2
3
3 1 2
Выходные данные
Sample 1
2.0
Sample 2
3.0

Объяснение: В первом примере Вася каждый раз выбирает для перемешивания первые два кубика. С вероятностью 2 после перемешивания кубики окажутся переставленными, и на этом процесс закончится. В среднем это произойдёт после двух перемешиваний.

Автор Евгений Капун
Источник Зимняя школа по программированию 2014, Харьков