Where the k-th can lie

heap tree counting contests

A heapsort of a photo’s pixels was stopped right after the first phase: the array of n pixels has already become a heap with the largest on top, and the extractions have not started. Cells are numbered from zero, the children of cell i are cells 2i + 1 and 2i + 2 (if they are less than n), and the brightness of each parent is greater than that of its children. All the brightnesses are different.

Where in such a heap can the k-th brightest pixel be? The brightest only at the root, the second brightest in one of the root’s children, and after that there are more and more options. For each query k count the cells for which there exists a heap of n different brightnesses with the k-th brightest pixel in exactly that cell.

In the second example n = 9600: this is the photo from the article, 120 × 80 pixels. One of the hidden tests is 19,073, the number of earthquakes in the USGS catalogue, and in others n goes up to 10¹⁸: going over the cells one by one will not work.

Input

The first line holds two numbers: n (1 ≤ n ≤ 10¹⁸) and the number of queries q (1 ≤ q ≤ 10⁵). Then come q lines, each with one number k (1 ≤ k ≤ n).

Output

For each query, on a separate line, the number of cells where the k-th brightest pixel can lie.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 11 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Start with the extreme cases. Where can the brightest lie? The second brightest? And the darkest, k = n? Draw a heap of seven cells and check the answer to the first example.

2Hint 2

Take a cell at depth d (the root has depth 0) whose subtree has s cells, itself included. How many elements are certainly brighter than what lies in it, and how many certainly darker? You get two conditions on k. Are they enough for such a heap to exist?

3Hint 3

In a complete binary tree the cells of one depth are almost alike: the subtrees on the left are full, on the right one level lower, and one in the middle is partial. So at each depth there are at most three different subtree sizes, and there are about 60 depths.

4The idea

All the ancestors of a cell are brighter than it: the heap property applied along the chain. All the descendants are darker, for the same reason. So the k-th brightest can stand in a cell at depth d with a subtree of s cells only if d ≤ k − 1 (there are enough bright ones for the ancestors) and s − 1 ≤ n − k (there are enough dark ones for the descendants).

These two conditions are also enough. We need to choose k − 1 cells for the brighter ones so that with each cell its parent is in the set too; then all the ancestors of our cell get into the set, and its subtree stays outside. Start with the chain of ancestors and add one cell at a time whose parent is already in the set, which is not in the subtree of our cell and is not the cell itself. Such cells do not run out while the set is smaller than n − s: everything outside the subtree is reachable from the root around it. It remains to hand out the brightest values to the set from the top down, the k-th to our cell, and the rest to the remaining cells from the top down; the heap property holds everywhere.

5Walkthrough

Let H = ⌊log₂ n⌋ be the depth of the last level, which has L = n − (2^H − 1) cells. The j-th cell of depth d < H has h = H − d levels below it; the full levels give 2^h − 1 cells, and from the last level it gets the cells numbered from j·2^h to (j + 1)·2^h − 1, of which only those less than L exist. So the first ⌊L/2^h⌋ cells of depth d have a subtree of 2^h+1 − 1, the next one (if L is not divisible by 2^h) has 2^h − 1 + (L mod 2^h), and the rest 2^h − 1. On the last level there are L leaves with a subtree of 1.

This gives a list of at most 3(H + 1) groups “depth, size, how many cells”. For a query k add up the groups with depth at most k − 1 and size at most n − k + 1. If k − 1 ≥ H, depth gets in nobody’s way, and the answer is the number of cells with a subtree of at most n − k + 1: it is given by a binary search over the groups sorted by size and prefix sums. If k ≤ H, there are at most 3k groups, and they can simply be gone over.

The second example shows the conditions taking turns. For k = 10 depth decides: the tenth brightest can lie only on the first ten levels, that is 1023 cells, and of them only the root will not do: the answer is 1022. A heap of 9600 cells has 14 levels, so from k = 14 on depth gets in nobody’s way, and the subtrees decide. At k = 4800 a cell can have at most 4800 descendants, and out drop the root and its left child, whose subtree has 5504 cells. At k = 9599 the 4800 leaves and the single cell with one child will do, and the darkest, k = 9600, only a leaf.

5+Solution

6Complexity

Preparation is O(log² n) for one n, a query O(log n): a binary search or going over at most 3k ≤ 3 log₂ n groups. Numbers up to 10¹⁸ fit in a 64-bit integer.

7Common mistakes

Only the depth condition. It seems that the k-th brightest can lie on any of the first k levels. But only darker ones must fit under it: the darkest pixel cannot lie above anyone. In the first example such an answer for k = 7 is 7 cells instead of 4.
Depth from one. The root has no ancestors, its children one: the condition is d ≤ k − 1 with the root at depth 0.
Walking the tree. With n up to 10¹⁸ the cells cannot be gone over one by one, and with q = 10⁵ you cannot even go over all the levels for each query with a nested loop over cells: you need groups of identical subtrees.

Algorithms behind it

SRT Algorithm Heapsort A heap right in the array: n log n in the worst case with no extra memory, the insurance of introsort and the Linux kernel's sort. O(n log n) 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems