#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define LL __int64

#define lowbit(x) (x&(-x))

using namespace std;

const int N=100050;

int sorted[N],n,m;

struct node{

    int val[N];

    int num[N];

    LL sum[N];

}tp[20];

LL ANS;

LL arrayTree[N];

void build(int lft,int rht,int p){

    if(lft==rht) return ;

    int i,mid=(lft+rht)/2;

    int isame=mid-lft+1,same=0;

    for(i=lft;i<=rht;i++){

        if(tp[p].val[i]<sorted[mid]) isame--;

    }

    int ln=lft,rn=mid+1;

    for(i = lft; i <= rht; i++) {

        if(i == lft) {

            tp[p].num[i] = 0;

            tp[p].sum[i]=0;

        } else {

            tp[p].num[i] = tp[p].num[i-1];

            tp[p].sum[i]=tp[p].sum[i-1];

        }

        if(tp[p].val[i] < sorted[mid]) {

            tp[p].num[i]++;

            tp[p].sum[i]+=tp[p].val[i];

            tp[p+1].val[ln++] = tp[p].val[i];

        }else if(tp[p].val[i] > sorted[mid]) {

            tp[p+1].val[rn++] = tp[p].val[i];

        }else {

            if(same < isame) {

                same++;

                tp[p].num[i]++;

                tp[p].sum[i]+=tp[p].val[i];

                tp[p+1].val[ln++] = tp[p].val[i];

            }else {

                tp[p+1].val[rn++] = tp[p].val[i];

            }

        }

    }

    build(lft, mid, p+1);

    build(mid+1, rht, p+1);

}

int query(int a, int b, int k, int p, int lft, int rht) {

    if(lft == rht) {

    	return tp[p].val[a];

    }

    LL sss=0;

    int s, ss, b2, bb, mid = (lft+rht)/2;

    if(a == lft) {

        s = tp[p].num[b];

        ss = 0;

        sss=tp[p].sum[b];

    } else {

        s = tp[p].num[b] - tp[p].num[a-1];

        ss = tp[p].num[a-1];

        sss=tp[p].sum[b]-tp[p].sum[a-1];

    }

    if(s >= k) {

        a = lft + ss;

        b = lft + ss + s - 1;

        return query(a, b, k, p+1, lft, mid);

    } else {

        bb = a - lft - ss;

        b2 = b - a + 1 - s;

        a = mid + bb + 1;

        b = mid + bb + b2;

        ANS+=sss;

        return query(a, b, k-s,p+1, mid+1, rht);

    }

}

void update(int i,int w){

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

		arrayTree[k]+=w;

	}

}

LL arraySum(int index){

	if(index==0) return 0;

	LL ret=0;

	for(int i=index;i>=1;i-=lowbit(i))

	ret+=arrayTree[i];

	return ret;

}

LL getsum(int l,int r){

//	cout<<arraySum(r)<<endl;

	return arraySum(r)-arraySum(l-1);

}

int main(){

	int T,Case=0;

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		memset(arrayTree,0,sizeof(arrayTree));

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

			scanf("%d",&tp[0].val[i]);

			sorted[i]=tp[0].val[i];

			update(i,sorted[i]);

		}

		ANS=0;

		sort(sorted+1,sorted+1+n);

		build(1,n,0);

		scanf("%d",&m);

		int l,r;

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

		for(int i=1;i<=m;i++){

			scanf("%d%d",&l,&r);

			l++,r++;

			LL spre=getsum(l,r);

			ANS=0;

			if((r-l+1)%2==0){

				int mid=query(l,r,(r-l+1)/2+1,0,1,n);

				printf("%I64d\n",spre-ANS-ANS);

			}

			else{

				int mid=query(l,r,(r-l+1)/2+1,0,1,n);

				printf("%I64d\n",spre-ANS-ANS-mid);

			}

		}

		puts("");

	}

	return 0;

}