P8487 "HGOI-1" Binary Search Ex.

This problem is an extra subtask of [div.2 B](https://www.luogu.com.cn/problem/P8481). It is not a full problem. The total score is $25$ points (after entering the main problem set, the full score is $100$ points). $\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 take either $\lfloor\dfrac{l+r}{2}\rfloor$ or $\lceil\dfrac{l+r}{2}\rceil$. So the indecisive student $\text{bh1234666}$ added randomness into his binary search code: each time, he randomly chooses one of them as $\textit{mid}$. Now $\text{bh1234666}$ tells you the index (starting from $0$) of the number he wants to find in the sequence (you can think of it as querying a number in an increasing sequence of indices $0 \sim n-1$). He wants to know, in the best possible luck, how many times the loop needs to run (that is, 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 gives an integer $n$ indicating the length of the sequence. The second line gives two integers $q$, $q_2$, indicating the number of queries, where $q$ is the number of queries given in the input, and $q_2$ is the number of queries generated by the data generator. The next line contains $q$ integers, indicating the numbers to query. Then the data generator provides $q_2$ queries (no need to read them).

Among the total of $q+q_2$ queries, let the answer to the $i$-th query be $ans_i$. Output an integer $\sum\limits_{i=1}^{q+q_2}i\times ans_i$ as the result.

### Explanation of Sample 1 The restored output is: $3\ 3\ 3$. Find $2$: Take $[1,5]$. Take $[1,3]$. Take $[3,3]$ (exit the loop). ### Explanation of Sample 2 The restored output is: $3\ 4\ 3\ 3\ 4$. #### Data Generator ```cpp #include using namespace std; #define ull unsigned long long ull sd = 111111111111111111ull, sd2, k = 1; ull qu, n, ans;//qu表示每次询问的位置。 inline ull get_q(int i) { sd = (sd2 ^ (sd2 >> 3)) + 998244353; return ((sd2 = sd ^ (sd > n; sd2 = n; while((k q2; init(); for(int i = 1; i > qu; ans += get_ans(qu) * i; } for(int i = 1; i