Minimum Additions to Set a Specific Binary Bit

You are given a positive integer ( n ) and an integer ( q ) representing the number of operations. For each operation, you are provided with a positive integer ( k ). Your task is to add a nonnegative integer ( x ) to ( n ) such that the ( k )-th bit (from right to left, 1-indexed) of ( n+x ) is ( 1 ) and ( x ) is minimized. After each operation, update ( n ) to ( n+x ).

Formally, let [ d = 2^{k-1} \quad \text{and} \quad M = 2^k. ] The ( k )-th bit of a number is ( 1 ) if and only if its residue modulo ( M ) is at least ( d ). For each operation, if [ n \bmod M < d, ] then set [ x = d - (n \bmod M). ] Otherwise, set ( x = 0 ).

After processing all ( q ) operations, output the sum of all choices of ( x ).

inputFormat

The first line contains two integers ( n ) and ( q ) separated by a space. Each of the next ( q ) lines contains a positive integer ( k ), representing a single operation.

outputFormat

Output a single integer, the sum of all ( x ) values over the ( q ) operations.

sample

1 1
2

1