CF1725D Deducing Sortability

Let's say Pak Chanek has an array $ A $ consisting of $ N $ positive integers. Pak Chanek will do a number of operations. In each operation, Pak Chanek will do the following: 1. Choose an index $ p $ ( $ 1 \leq p \leq N $ ). 2. Let $ c $ be the number of operations that have been done on index $ p $ before this operation. 3. Decrease the value of $ A_p $ by $ 2^c $ . 4. Multiply the value of $ A_p $ by $ 2 $ . After each operation, all elements of $ A $ must be positive integers. An array $ A $ is said to be sortable if and only if Pak Chanek can do zero or more operations so that $ A_1 < A_2 < A_3 < A_4 < \ldots < A_N $ . Pak Chanek must find an array $ A $ that is sortable with length $ N $ such that $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ is the minimum possible. If there are more than one possibilities, Pak Chanek must choose the array that is lexicographically minimum among them. Pak Chanek must solve the following things: - Pak Chanek must print the value of $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ for that array. - $ Q $ questions will be given. For the $ i $ -th question, an integer $ P_i $ is given. Pak Chanek must print the value of $ A_{P_i} $ . Help Pak Chanek solve the problem. Note: an array $ B $ of size $ N $ is said to be lexicographically smaller than an array $ C $ that is also of size $ N $ if and only if there exists an index $ i $ such that $ B_i < C_i $ and for each $ j < i $ , $ B_j = C_j $ .

The first line contains two integers $ N $ and $ Q $ ( $ 1 \leq N \leq 10^9 $ , $ 0 \leq Q \leq \min(N, 10^5) $ ) — the required length of array $ A $ and the number of questions. The $ i $ -th of the next $ Q $ lines contains a single integer $ P_i $ ( $ 1 \leq P_1 < P_2 < \ldots < P_Q \leq N $ ) — the index asked in the $ i $ -th question.

Print $ Q+1 $ lines. The $ 1 $ -st line contains an integer representing $ A_1 + A_2 + A_3 + A_4 + \ldots + A_N $ . For each $ 1 \leq i \leq Q $ , the $ (i+1) $ -th line contains an integer representing $ A_{P_i} $ .

In the first example, the array $ A $ obtained is $ [1, 2, 3, 3, 4, 4] $ . We can see that the array is sortable by doing the following operations: - Choose index $ 5 $ , then $ A = [1, 2, 3, 3, 6, 4] $ . - Choose index $ 6 $ , then $ A = [1, 2, 3, 3, 6, 6] $ . - Choose index $ 4 $ , then $ A = [1, 2, 3, 4, 6, 6] $ . - Choose index $ 6 $ , then $ A = [1, 2, 3, 4, 6, 8] $ .