Problem H: 二进制与一

Memory Limit:128 MB Time Limit:1.000 S
Submit:9 Solved:4

Description

给定一个正整数 n,以及操作次数 q。对于每次操作,给出一个正整数 k,要求:让 n 加上一个非负整数 x,使得 n 在二进制下的第 k 位(从右往左数)是 1,并在符合要求的情况下,令 x 最小。

请注意,每次操作都会让 n 变为 n+x,会影响后续操作。

小山需要求出,所有的 x 之和是多少。

Input

输入共 q+1 行。

第一行两个整数 n 和 q。
接下来 q 行,每行一个正整数 k,表示要让 n 在二进制下从右往左数的第 k 位是 1。

Output

一行一个整数,表示所有的 x 之和。

Sample Input Copy

5 3
2
3
4

Sample Output Copy

3

HINT

样例 1 说明
5 在二进制下是 101。

对于第一次操作,需要让 101 的第二位变为 1,则需让 101 加上 1,变为 110;
对于第二次操作,需要让 110 的第三位是 1,由于 110 的第三位本身就是一,所以无需改变;
第三次操作同理,需要让 110 加上 2。
最终输出结果是 1+0+2=3。


对于 100% 的数据,1≤n<232,1≤q≤105,1≤k≤32。

Source/Category