P8481 "HGOI-1" Binary search

$\text{bh1234666}$ is learning [binary search](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin).

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: ```cpp int find(int *num,int x,int len) { int l=0,r=len-1,mid,cnt=0,w; while(l

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.

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

### 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](https://www.luogu.com.cn/problem/P8487). Translated by ChatGPT 5