Background

This problem is an extra sub-task of div.2 B, not a complete problem, with a total score of $25$ points (after entering the main repository, the full score is $100$ points).

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

Problem Description

As we know, in binary search, $\text{mid}$ can be calculated as $\lfloor\dfrac{l+r}{2}\rfloor$ or $\lceil\dfrac{l+r}{2}\rceil$. $\text{bh1234666}$, who has difficulty making choices, has added randomness to his binary search code, selecting one of these two methods randomly each time for $\textit{mid}$.

Now, $\text{bh1234666}$ tells you the index of the number he wants to find in the sequence (starting from $0$, which can be understood as querying a number in a sorted sequence from $0$ to $n-1$). He wants to know the minimum number of iterations required in the best-case scenario (i.e., the smallest possible final value of $\textit{cnt}$).

Iteration:

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 above two codes are equivalent.

Input Format

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

The second line contains two integers $q$ and $q_2$, representing the number of queries, where $q$ is the number of input queries, and $q_2$ is the number of queries generated by the data generator.

The next line contains $q$ integers representing the numbers to be queried.

The data generator will provide $q_2$ queries (no need to read in).

Output Format

Among the total $q + q_2$ queries, let the answer for the $i$-th query be $ans_i$.

Please output an integer $\sum\limits_{i=1}^{q+q_2}i \times ans_i$ as the answer.

Sample Input and Output

Input Sample #1

10
3 0
2 6 8

Output Sample #1

18

Input Sample #2

13
5 0
0 1 4 6 11

Output Sample #2

52

Input Sample #3

1928374
10 1000000
193 3489 238 438 8 912 83 19 12489 10

Output Sample #3

10000215403302

Notes

Sample 1 Explanation

Restored output: $3\ 3\ 3$.

Searching for $2$:

Range $[1, 5]$.

Range $[1, 3]$.

Range $[3, 3]$ (exit loop).

Sample 2 Explanation

Restored output: $3\ 4\ 3\ 3\ 4$.

Data Generator

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull sd = 111111111111111111ull, sd2, k = 1;
ull qu, n, ans; // qu represents the position of each query.
inline ull get_q(int i)
{
    sd = (sd2 ^ (sd2 >> 3)) + 998244353;
    return ((sd2 = sd ^ (sd << 37)) & k) + ((i & 1) ? 0 : (n - k - 1));
}
int q, q2;
void init()
{
    // Put your code here or not.
}
inline ull get_ans(ull x)
{
    // Put your code here.
}
int main()
{
    cin >> n;
    sd2 = n;
    while ((k << 1) <= n + 1) k <<= 1;
    k -= 1;
    cin >> q >> q2;
    init();
    for (int i = 1; i <= q; i++)
    {
        cin >> qu;
        ans += get_ans(qu) * i;
    }
    for (int i = 1; i <= q2; i++)
    {
        qu = get_q(i);
        ans += get_ans(qu) * (i + q);
    }
    cout << ans << endl;
    return 0;
}

Data Range and Constraints

This problem does not use bundled testing; the score is the sum of the points for each test case. Data has gradients as shown in the table below.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{ExTest} & \textbf{Score} & \textbf{Special Constraints} \cr\hline 1 & 5 & n, q_2 \le 2^{20}\cr\hline 2 & 5 & n \le 2^{30}, q_2 \le 2 \times 10^6 \cr\hline 3 & 5 & n \le 2^{40}, q_2 \le 5 \times 10^6 \cr\hline 4 & 5 & n \le 2^{50}, q_2 \le 2 \times 10^7 \cr\hline 5 & 5 & n \le 2^{60}, q_2 \le 2 \times 10^8 \cr\hline \end{array} $$
For $100\%$ of the data, $1 \le n \le 2^{60}$, $1 \le q + q_2 \le n$, $q \le 2^{20}$, $q_2 \le 2 \times 10^8$.

This problem guarantees that the time limit is more than twice that of the standard solution and that using the provided template can pass this problem.

见题面 Input 部分

见题面 Output 部分