D. Deducing Sortability
binary search; bitmasks; math
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: Choose an index \(p\) (\(1 \leq p \leq N\)). Let \(c\) be the number of operations that have been done on index \(p\) before this operation. Decrease the value of \(A_p\) by \(2^c\). 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]\).