28731번 - Этажи 스페셜 저지다국어

문제

Артур Флек живет в очень старом доме: лифт не работает, а многие таблички с номерами этажей пришли в негодность. Артур очень устал и хочет поскорее попасть в свою квартиру.

В доме есть $n$ этажей, пронумерованных от 1ドル$ до $n$. Между соседними этажами можно перемещаться по лестнице. Артур живет на этаже с номером $k$.

На некоторых этажах висят таблички с указанием номера этого этажа. Артур знает, что таблички присутствуют на $t$ этажах с номерами $a_1, a_2, \ldots, a_t$. Также известно, что на этажах с номерами 1ドル$ и $n$ таблички есть.

Придя домой, Артур поднимался по лестнице, но задумался, и поэтому теперь он не знает, на каком этаже оказался. На каждом этаже он мог оказаться с вероятностью $\frac{1}{n}$. Артур не отличает этажи друг от друга и может ориентироваться только по табличкам с номерами. В том числе, если на этаже номер $k$ нет таблички, он не может отличить его от остальных этажей без табличек. Он хочет совершить как можно меньше переходов между этажами, попасть на этаж с номером $k$ и быть уверенным, что он оказался на этаже с номером $k$. Артур не очень сообразительный, поэтому пока он не дойдет до этажа с табличкой, он не может сделать никаких предположений о номере этажа, на котором сейчас находится.

Помогите Артуру найти оптимальную стратегию действий и определите математическое ожидание количества переходов между этажами, которое ему придется совершить.

입력

В первой строке даны три целых числа $n,ドル $k$ и $t$ --- количество этажей в доме, этаж, на котором живет Артур, и количество этажей с табличками (2ドル \le t \le n \le 100,000円$; 1ドル \le k \le n$).

Вторая строка содержит $t$ целых чисел $a_1, \ldots, a_t$ --- номера этажей, на которых есть таблички. Гарантируется, что 1ドル = a_1 < a_2 < \ldots < a_t = n$.

출력

Выведите единственное вещественное число --- математическое ожидание количества переходов между этажами, которое придется совершить Артуру, чтобы попасть на этаж с номером $k$ при оптимальной стратегии, если изначально он может находиться на любом этаже с одинаковой вероятностью.

Ответ будет засчитан, если его абсолютная или относительная погрешность не превышает 10ドル^{-6}$.

제한

노트

В первом тесте, если Артур изначально находится на этаже с номером 1ドル,ドル 2ドル$ или 4ドル,ドル он сразу знает номер текущего этажа, и его оптимальной стратегией будет пойти в правильном направлении до желаемого этажа 3ドル$. Если же Артур изначально находился на этаже номер 3ドル,ドル он не знает об этом, потому что на нем нет таблички. Одной из оптимальных стратегий в этом случае будет подняться на один этаж вверх, узнать, что Артур оказался на этаже номер 4ドル,ドル потому что на нем есть табличка, и спуститься обратно на один этаж. Поэтому, ответом будет $\frac{2 + 1 + 2 + 1}{4} = 1.5$.

Во втором тесте, если Артур оказался на этаже с номером 1ドル,ドル 3ドル$ или 5ドル,ドル он знает его номер, и оптимальной стратегией будет просто пойти в правильном направлении до этажа с номером 3ドル$. Иначе, он оказался на этаже с номером 2ドル$ или 4ドル$. В таком случае оптимальной стратегией будет спуститься на один этаж вниз. Если Артур был на этаже с номером 2ドル,ドル он попадет на этаж с номером 1ドル,ドル на котором висит табличка, поэтому дальше он просто сделает еще 2ドル$ перехода и попадет на желаемый этаж номер 3ドル$. Если же Артур был на этаже номер 4ドル,ドル после перехода он окажется на этаже номер 3ドル,ドル на котором висит табличка, поэтому он поймет, что пришел на желаемый этаж, и больше никуда не пойдет. В этом случае математическое ожидание количества переходов будет $\frac{2 + 3 + 0 + 1 + 2}{5} = 1.6$.