Distanciament aviar (pendent de revisar) X68155

En un arbre hi viuen $2^n - 1$ ocells, cadascun en el seu niu. Numerem els ocells de $1$ a $2^n - 1$. El niu que està més avall és el de l’ocell $1$, i està just on el tronc es bifurca en dos. A partir d’aquí, anant cap amunt, cada branca es va bifurcant en dos. A cada bifurcació, un ocell té un niu. A més, per a cada ocell $i$ amb $1 \leq i \leq 2^{n-1} - 1$, els dos nius que té a sobre, seguint les dues subbranques, són els dels ocells $2i$ i $2i+1$. Així, l’únic ocell que està a altura $1$ és l’ocell $1$, els que estan a altura $2$ són els ocells $2$ i $3$, els que estan a altura $3$ són els ocells $4, 5, 6, 7$, i així succesivament fins a altura $n$.

L’ocell $1$ ha contret una malaltia molt contagiosa. Si un ocell $i$ agafa la malaltia, la transmetrà als dos ocells de sobre (excepte si $i$ està a altura màxima). Alguns dels ocells, espantats, marxen del seu niu. Gràcies a això, no agafen la malaltia i la malaltia no es propaga als ocells de sobre.

Nota: Aquest problema està pendent de revisar

Entrada

L’entrada comença amb un enter $n$, indicant que hi ha $2^n - 1$ ocells, i un enter $m$, el nombre d’ocells que fugen. A continuació venen $m$ nombres diferents $a_1, a_2 \dots a_m$, els ocells que fugen. Direm que un ocell $x$ és inferior a un ocell $y$ si per anar del niu de l’ocell $y$ al de l’ocell $1$ seguint les branques, cal passar pel niu de l’ocell $x$. Se’t garantitza que $a_i$ no és inferior a $a_j$ per a cap parell $(i, j)$ amb $i \neq j$.

Sortida

Escriviu un enter: el nombre d’ocells que agafen la malaltia.

Puntuació

• 200 punts: Casos amb $n \leq 16$

• 400 punts: Casos amb $n \leq 29, m \leq 10^5$