Артур Флек живет в очень старом доме: лифт не работает, а многие таблички с номерами этажей пришли в негодность. Артур очень устал и хочет поскорее попасть в свою квартиру.
В доме есть $$$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}$$$.
4 3 3 1 2 4
1.5
5 3 3 1 3 5
1.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$$$.