Background

$\text{bh1234666}$ is learning binary search.

Problem Description

As everyone knows, when computing $\text{mid}$ in binary search, you can use $\lfloor\dfrac{l+r}{2}\rfloor$ or $\lceil\dfrac{l+r}{2}\rceil$. So the student $\text{bh1234666}$, who cannot decide between the two, added randomization to their binary search code: each time, they randomly choose one of them as $\textit{mid}$.

Note that choosing different mid will also affect other parameters. Please follow the code.

Now $\text{bh1234666}$ gives you the sequence used in the binary search (guaranteed to be strictly increasing) and the number they want to find (guaranteed to be in the sequence). They want to know, in the best possible luck, how many iterations the loop needs to run (i.e., the minimum possible final value of $\textit{cnt}$ in the code).

Loop:

int find(int *num,int x,int len)
{
	int l=0,r=len-1,mid,cnt=0,w;
	while(l<r)
	{
		cnt++;
		w=rand()%2;
		mid=(l+r+w)/2;
		if(num[mid]-w<x) l=mid+!w;
		else r=mid-w;
	}
	return mid;
}

Recursion:

int cnt;
int get(int *num,int x,int l,int r)
{
	if(l==r) return l;
	cnt++;
	int w=rand()%2;
	int mid=(l+r+w)/2;
	if(num[mid]-w<x) return get(num,x,mid+!w,r);
	else return get(num,x,l,mid-w);
}
int find(int *num,int x,int len)
{
	cnt=0;
	return get(num,x,0,len-1);
}

Note: The two pieces of code above are completely equivalent.

Here is a further explanation of the role of $w$ in the code above.

For example, for the interval $[0,7]$, there are $8$ elements. Although the value of $mid$ changes with the value of $w$, the final chosen interval must be either $[0,3]$ or $[4,7]$. You can simulate it yourself using the code above.

For the interval $[0,6]$, there are $7$ elements. The value of $\textit{mid}$ is independent of $w$, but the values of $l$ and $r$ will be affected by $w$. The final chosen interval may be $[0,2]$, $[3,6]$ ($w=1$) or $[0,3]$, $[4,6]$ ($w=0$).

Input Format

The first line contains an integer $n$, the length of the sequence.

The second line contains $n$ strictly increasing integers, the sequence of $\text{bh1234666}$.

The third line contains an integer $q$, the number of queries.

The next $q$ lines each contain an integer, the number to query.

Output Format

For each query, output an integer representing the minimum number of loop iterations.

10
1 2 4 6 7 8 10 13 15 17
3
4
10
15

3
3
3

13
1 2 4 6 10 12 19 23 45 99 101 123 134
5
1
2
10
19
123

3
4
3
3
4

Hint

Sample 1 Explanation

Find $4$:

Take $[1,5]$.

Take $[1,3]$.

Take $[3,3]$ (exit the loop).

Sample 2 Explanation

Query the position of $10$.

$$[1,13] \stackrel{w=0}{\longrightarrow} [1,7]\stackrel{w=0}{\longrightarrow}[5,7] \stackrel{w=1}{\longrightarrow} [5,5]$$

Constraints and Notes

This problem uses bundled tests. There are $3$ $\text{subtask}$ in total, and the final score is the sum of the scores of all $\text{subtask}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \text{Special Limits} \cr\hline 1 & 25 & n \le 20 \cr\hline 2 & 35 & n=2^k(k \in \mathbf{N}) \cr\hline 3 & 40 & \cr\hline \end{array}$$

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2^{20}$, $1 \le q \le 100$, $1 \le num_i \le 10^9$.

This problem has an extra sub.

Translated by ChatGPT 5