[Solution] Deducing Sortability Codeforces Solution

D. Deducing Sortability

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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≤𝑝≤𝑁$1\le p\le 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𝑐$2^c$.
4. Multiply the value of 𝐴𝑝$A_p$ by 2$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 𝐴1<𝐴2<𝐴3<𝐴4<…<𝐴𝑁$A_1<A_2<A_3<A_4<\dots <A_N$.

Pak Chanek must find an array 𝐴$A$ that is sortable with length 𝑁$N$ such that 𝐴1+𝐴2+𝐴3+𝐴4+…+𝐴𝑁$A_1+A_2+A_3+A_4+\dots +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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Pak Chanek must solve the following things:

• Pak Chanek must print the value of 𝐴1+𝐴2+𝐴3+𝐴4+…+𝐴𝑁$A_1+A_2+A_3+A_4+\dots +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$.

Input

The first line contains two integers 𝑁$N$ and 𝑄$Q$ (1≤𝑁≤109$1\le N\le {10}^9$, 0≤𝑄≤min(𝑁,105)$0\le Q\le 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≤𝑃1<𝑃2<…<𝑃𝑄≤𝑁$1\le P_1<P_2<\dots <P_Q\le N$) — the index asked in the 𝑖$i$-th question.

Output

Print 𝑄+1$Q+1$ lines. The 1$1$-st line contains an integer representing 𝐴1+𝐴2+𝐴3+𝐴4+…+𝐴𝑁$A_1+A_2+A_3+A_4+\dots +A_N$. For each 1≤𝑖≤𝑄$1\le i\le Q$, the (𝑖+1)$(i+1)$-th line contains an integer representing 𝐴𝑃