## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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\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}^{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}<\dots <{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}+\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:-  👉
👇👇👇👇👇

Pak Chanek must solve the following things:

• Pak Chanek must print the value of ${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${B}_{j}={C}_{j}$.

Input

The first line contains two integers $N$ and $Q$ ($1\le N\le {10}^{9}$$0\le Q\le min\left(N,{10}^{5}\right)$) — 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\le {P}_{1}<{P}_{2}<\dots <{P}_{Q}\le N$) — the index asked in the $i$-th question.

Output

Print $Q+1$ lines. The $1$-st line contains an integer representing ${A}_{1}+{A}_{2}+{A}_{3}+{A}_{4}+\dots +{A}_{N}$. For each $1\le i\le Q$, the $\left(i+1\right)$-th line contains an integer representing