Приближается самое главное событие года — финал чемпионата мира The Innernational по игре Cota 2. В нём участвуют $$$2^n$$$ команд, среди которых нужно определить одну лучшую.
Матчи будут проводиться по олимпийской системе до двух поражений (внимательно прочитайте условие, даже если знаете, что это такое). По итогам жеребьевки, команды получили номера от $$$1$$$ до $$$2^n$$$, после чего будут играть друг с другом встречи один-на-один. Все команды начинают турнир в верхней сетке.
В матчах верхней сетки в каждом раунде один раз играют пары соседних (из ещё не потерпевших поражение) команд в порядке жеребьевки. Победитель проходит дальше, а проигравший падает в нижнюю сетку.
Нижняя сетка начинается с $$$2^{n-1}$$$ команд, проигравших первую же игру верхней сетки. Каждый раунд нижней сетки состоит из двух игр. Для каждого раунда, в первой игре раунда, $$$2^k$$$ команд нижней сетки играют друг с другом в порядке жеребьевки. $$$2^{k-1}$$$ проигравших выбывают с турнира, а $$$2^{k-1}$$$ победителей играют с $$$2^{k-1}$$$ командами, потерпевшими поражение в этом раунде верхней сетки (снова в порядке жеребьевки). По итогам каждого раунда и в верхней, и в нижней сетке остается одинаковое число участников — по $$$2^{k-1}$$$. Смотрите на картинку для более точного понимания условия.
Когда в верхней и нижней сетках остается по одной команде, они играют между собой гранд-финал и турнир заканчивается.
Вам интересны команды, получившие по результатам жеребьевки номера $$$a_1, a_2, ..., a_k$$$. Вам хочется увидеть как можно больше матчей, где играет хотя бы одна из интересных вам команд. Вы можете повлиять на результат любого матча так, чтобы в нем выиграла команда на ваше усмотрение. Какое максимально возможное количество матчей с участием хотя бы одной из интересных вам команд может быть сыграно в чемпионате?
В первой строке даны два числа $$$n, k$$$ — размер сетки ($$$2^n$$$ команд играют в чемпионате) и количество интересных вам команд ($$$2 \le n \le 17; 0 \le k \le 2^n$$$).
Во второй строке даны $$$k$$$ различных целых чисел $$$a_1, \ldots, a_k$$$ — номера этих команд по результатам жеребьевки ($$$1 \le a_i \le 2^n$$$).
Выведите одно число — максимально возможное число матчей, в которых будет играть хотя бы одна интересная вам команда.
3 1 6
6
3 3 1 7 8
11
3 4 1 3 5 7
14
На схеме турнира из примера каждый матч отмечен английской буквой (от $$$a$$$ до $$$n$$$). Победитель каждого $$$i$$$-го матча обозначается $$$Wi$$$, проигравший — $$$Li$$$. Интересные команды выделены красным фоном.
В первом примере, интересная команда $$$6$$$ сыграет максимальное количество матчей если в первом же матче верхней сетки (матч $$$c$$$) проиграет, но выиграет все остальные матчи в нижней сетке (матчи $$$h, j, l, m$$$) и таким образом попадёт в гранд-финал турнира.
Во втором примере, интересные команды $$$7$$$ и $$$8$$$ должны сыграть друг против друга в первом матче верхней сетки (матч $$$d$$$). После этого, команда $$$8$$$ может дойти до гранд-финала без поражений, а команды $$$1$$$ и $$$7$$$ будут соревноваться в нижней сетке.
В третьем примере, правильно распределившиеся интересные команды смогут поучаствовать во всех матчах турнира.
