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。
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。