Double Elimination

题意翻译

$2^n$ 个队伍将要通过双败淘汰制来决定冠军。 所有队伍被标号 $1$ 到 $2^n$，它们将进行若干场一对一的比赛。最开始时，他们都在胜者组。 所有的在胜者组的比赛只会在当前没有输过任何比赛的队伍之间进行。所有队伍会被按照编号顺序安排比赛。在胜者组的获胜者将晋级下一轮的胜者组的比赛，失败者将会在下一轮参加败者组的比赛。 第一轮的败者组比赛由 $2^{n-1}$ 个输了第一场胜者组比赛的队伍进行。每一轮的败者组比赛要比赛两次。每一轮的第一次比赛有 $2^k$ 个队伍互相比赛，第二次比赛是由第一次比赛的 $2^{k-1}$ 个获胜队伍和 $2^{k-1}$ 个在这一轮胜者组比赛中失败的队伍互相比赛。（都是按照编号顺序进行比赛）结果是每一轮之后胜者组和败者组都将只剩下 $2^{k-1}$ 个队伍进行比赛。你可以阅读样例以更好的理解题目。 最终，胜者场唯一留下的队伍的和败者场唯一留下的队伍将比赛决出全场冠军。 你是编号 $a_1,a_2,\cdots,a_k$ 队伍的粉丝，你希望你喜欢的队伍参加的比赛尽可能多。幸运的是，你可以用某些方法操纵每场比赛的赢家，求你有你喜欢的队伍的比赛数最多是多少。 $2\le n\le 17, 0\le k\le 2^{n}$. (Translated by [@Ryoku](https://www.luogu.com.cn/user/34238))

题目描述

The biggest event of the year – Cota 2 world championship "The Innernational" is right around the corner. $ 2^n $ teams will compete in a double-elimination format (please, carefully read problem statement even if you know what is it) to identify the champion. Teams are numbered from $ 1 $ to $ 2^n $ and will play games one-on-one. All teams start in the upper bracket. All upper bracket matches will be held played between teams that haven't lost any games yet. Teams are split into games by team numbers. Game winner advances in the next round of upper bracket, losers drop into the lower bracket. Lower bracket starts with $ 2^{n-1} $ teams that lost the first upper bracket game. Each lower bracket round consists of two games. In the first game of a round $ 2^k $ teams play a game with each other (teams are split into games by team numbers). $ 2^{k-1} $ loosing teams are eliminated from the championship, $ 2^{k-1} $ winning teams are playing $ 2^{k-1} $ teams that got eliminated in this round of upper bracket (again, teams are split into games by team numbers). As a result of each round both upper and lower bracket have $ 2^{k-1} $ teams remaining. See example notes for better understanding. Single remaining team of upper bracket plays with single remaining team of lower bracket in grand-finals to identify championship winner. You are a fan of teams with numbers $ a_1, a_2, ..., a_k $ . You want the championship to have as many games with your favourite teams as possible. Luckily, you can affect results of every championship game the way you want. What's maximal possible number of championship games that include teams you're fan of?

输入输出格式

输入格式

First input line has two integers $ n, k $ — $ 2^n $ teams are competing in the championship. You are a fan of $ k $ teams ( $ 2 \le n \le 17; 0 \le k \le 2^n $ ). Second input line has $ k $ distinct integers $ a_1, \ldots, a_k $ — numbers of teams you're a fan of ( $ 1 \le a_i \le 2^n $ ).

输出格式

Output single integer — maximal possible number of championship games that include teams you're fan of.

输入输出样例

输入样例 #1

3 1
6

输出样例 #1

6

输入样例 #2

3 3
1 7 8

输出样例 #2

11

输入样例 #3

3 4
1 3 5 7

输出样例 #3

14

说明

On the image, each game of the championship is denoted with an English letter ( $ a $ to $ n $ ). Winner of game $ i $ is denoted as $ Wi $ , loser is denoted as $ Li $ . Teams you're a fan of are highlighted with red background. In the first example, team $ 6 $ will play in 6 games if it looses the first upper bracket game (game $ c $ ) and wins all lower bracket games (games $ h, j, l, m $ ). In the second example, teams $ 7 $ and $ 8 $ have to play with each other in the first game of upper bracket (game $ d $ ). Team $ 8 $ can win all remaining games in upper bracket, when teams $ 1 $ and $ 7 $ will compete in the lower bracket. In the third example, your favourite teams can play in all games of the championship. 

题意翻译

$2^n$ 个队伍将要通过双败淘汰制来决定冠军。 所有队伍被标号 $1$ 到 $2^n$，它们将进行若干场一对一的比赛。最开始时，他们都在胜者组。 所有的在胜者组的比赛只会在当前没有输过任何比赛的队伍之间进行。所有队伍会被按照编号顺序安排比赛。在胜者组的获胜者将晋级下一轮的胜者组的比赛，失败者将会在下一轮参加败者组的比赛。 第一轮的败者组比赛由 $2^{n-1}$ 个输了第一场胜者组比赛的队伍进行。每一轮的败者组比赛要比赛两次。每一轮的第一次比赛有 $2^k$ 个队伍互相比赛，第二次比赛是由第一次比赛的 $2^{k-1}$ 个获胜队伍和 $2^{k-1}$ 个在这一轮胜者组比赛中失败的队伍互相比赛。（都是按照编号顺序进行比赛）结果是每一轮之后胜者组和败者组都将只剩下 $2^{k-1}$ 个队伍进行比赛。你可以阅读样例以更好的理解题目。 最终，胜者场唯一留下的队伍的和败者场唯一留下的队伍将比赛决出全场冠军。 你是编号 $a_1,a_2,\cdots,a_k$ 队伍的粉丝，你希望你喜欢的队伍参加的比赛尽可能多。幸运的是，你可以用某些方法操纵每场比赛的赢家，求你有你喜欢的队伍的比赛数最多是多少。 $2\le n\le 17, 0\le k\le 2^{n}$. (Translated by [@Ryoku](https://www.luogu.com.cn/user/34238))