Дано число $$$n$$$ и перестановка чисел $$$p_1, p_2, ... , p_n$$$. Также даны два числа $$$a, b$$$. Есть операции 2 типов. Первый тип: поменять местами любых два элемента перестановки за $$$a$$$ монет. Второй тип: поменять порядок элементов перестановки на случайный за $$$b$$$ монет. Можно совершить сколько угодно операций каждого типа в любом порядке. Необходимо получить из перестановки тождественную перестановку ($$$1, 2, ... , n$$$). Нужно найти для заданной перестановки при оптимальной стратегии матожидание количества потраченных монет для достижения цели.
Первая строка входного файла содержит числа $$$n, a, b$$$, разделенные пробелами.
Вторая строка содержит перестановку $$$p$$$ длины $$$n$$$, элементы разделены пробелами.
$$$$$$1 \le n \le 20$$$$$$ $$$$$$1 \le a, b \le 1000$$$$$$ $$$$$$1 \le p_i \le n$$$$$$
Выведите одно число: искомое матожидание количества потраченных монет. Ваш ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает $$$10^{-9}$$$.
2 5 5 1 2
0.00000000000000000000
2 5 1 2 1
2.00000000000000000000
