Problem Description

You are given N positive integers, denoted as x0, x1 ... xN-1. Then give you some intervals [l, r]. For each interval, you need to find a number x to make as small as possible!

 

Input

The first line is an integer T (T <= 10), indicating the number of test cases. For each test case, an integer N (1 <= N <= 100,000) comes first. Then comes N positive integers x (1 <= x <= 1,000, 000,000) in the next line. Finally, comes an integer Q (1 <= Q <= 100,000), indicting there are Q queries. Each query consists of two integers l, r (0 <= l <= r < N), meaning the interval you should deal with.

 

Output

For the k-th test case, first output “Case #k:” in a separate line. Then output Q lines, each line is the minimum value of  . Output a blank line after every test case.

 

Sample Input

 

Sample Output

 

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<string>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 1000000001

#define MOD 1000000007

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define pi acos(-1.0)

using namespace std;

const int MAXN = ;

int num[][MAXN],cnt[][MAXN],sor[MAXN],n,leftnum;

ll sum[][MAXN],leftsum,all[MAXN];//sum记录第d层 第i个数之前小于sor[m]的和

void build(int l,int r,int d)

{

    if(l == r){

        return ;

    }

    int m = (l + r) >> ;

    int same_m = m - l + ;

    for(int i = l; i <= r; i++){

        if(num[d][i] < sor[m])same_m --;

    }

    int cnt_small = ;

    int pl,pr;

    ll val = ;

    pl = l,pr = m + ;

    for(int i = l; i <= r; i++){

        if(num[d][i] < sor[m]){

            cnt_small ++;

            val += num[d][i];

            sum[d][i] = val;

            cnt[d][i] = cnt_small;

            num[d+][pl++] = num[d][i];

        }

        else if(num[d][i] == sor[m] && same_m){

            same_m --;

            cnt_small ++;

            val += num[d][i];

            sum[d][i] = val;

            cnt[d][i] = cnt_small;

            num[d+][pl++] = num[d][i];

        }

        else {

            sum[d][i] = val;

            cnt[d][i] = cnt_small;

            num[d+][pr++] = num[d][i];

        }

    }

    build(l,m,d+);

    build(m+,r,d+);

}

ll query(int L,int R,int k,int l,int r,int d)

{

    if(l == r){

        return num[d][l];

    }

    int m = (l + r) >> ;

    int s,ss;

    ll val = ;

    if(l == L)s = , val = sum[d][R];

    else s = cnt[d][L-], val = sum[d][R] - sum[d][L-];

    ss = cnt[d][R] - s;

    if(ss >= k){

        int newl = l + s;

        int newr = l + s + ss - ;

        return query(newl,newr,k,l,m,d+);

    }

    else {

        leftnum += ss;//进入左孩子不用处理，进入右孩子时 就要加上左孩子的值

        leftsum += val;

        int a = L - l - s;

        int b = R - L +  - ss;

        int newl = m +  + a;

        int newr = m +  + a + b - ;

        return query(newl,newr,k - ss,m+,r,d+);

    }

}

int main()

{

    int t,ff = ;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        memset(all,,sizeof(all));

        memset(num,,sizeof(num));

        for(int i = ; i <= n; i++){

            scanf("%d",&num[][i]);

            sor[i] = num[][i];

            all[i] = all[i-] + sor[i];

        }

        sort(sor + ,sor + n + );

        build(,n,);

        int q,x,y;

        scanf("%d",&q);

        printf("Case #%d:\n",++ff);

        while(q--){

            scanf("%d%d",&x,&y);

            x += ;

            y += ;

            int len = (y - x + );

            ll tp;

            leftnum = ;

            leftsum = ;

            if(len % ){

                int k = (len + ) >> ;

                tp = query(x,y,k,,n,);

            }

            else {

                int k = len >> ;

                tp = query(x,y,k,,n,);

            }

            //cout<<tp<<' '<<leftnum<<' '<<leftsum<<' '<<all[y]<<' '<<all[x+leftnum]<<endl;

            ll ans = tp * (leftnum + ) - (leftsum + tp) + (all[y] - all[x - ] - (leftsum + tp)) - (y - x +  - (leftnum + )) * tp;

            printf("%lld\n",ans);

        }

        printf("\n");

    }

    return ;

}