//Accepted 28904 KB 781 ms
//划分树
//所求x即为l,r区间排序后的中位数t
//然后求出小于t的数的和sum1,这个可以用划分树做
//求出整个区间的和sum,可以用O(1)的数组做
//ans=(k-1)*t-sum1+sum-sum1-(l-r+1-k+1)*t
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
/**
* This is a documentation comment block
* 如果有一天你坚持不下去了,就想想你为什么走到这儿!
* @authr songt
*/
;
struct node
{
int val[imax_n];
int num[imax_n];
__int64 sum[imax_n];
}f[];
int a[imax_n];
__int64 all[imax_n];
int sorted[imax_n];
int n;
void build(int t,int l,int r)
{
if (l==r) return ;
;
;
;
for (int i=l;i<=r;i++)
{
if (f[t].val[i]<sorted[mid]) isame--;
}
int ln=l;
;
for (int i=l;i<=r;i++)
{
if (i==l)
{
f[t].num[i]=;
f[t].sum[i]=;
}
else
{
f[t].sum[i]=f[t].sum[i-];
f[t].num[i]=f[t].num[i-];
}
if (f[t].val[i]<sorted[mid])
{
f[t].num[i]++;
f[t].sum[i]+=f[t].val[i];
f[t+].val[ln++]=f[t].val[i];
}
else if (f[t].val[i]>sorted[mid])
{
f[t+].val[rn++]=f[t].val[i];
}
else
{
if (same<isame)
{
same++;
f[t].num[i]++;
f[t].sum[i]+=f[t].val[i];
f[t+].val[ln++]=f[t].val[i];
}
else
{
f[t+].val[rn++]=f[t].val[i];
}
}
}
build(t+,l,mid);
build(t+,mid+,r);
}
__int64 sum=;
int lnum;
int query(int t,int l,int r,int a,int b,int k)
{
int s,ss;
if (l==r) return f[t].val[l];
;
__int64 tsum=;
if (a==l)
{
ss=;
s=f[t].num[b];
tsum=f[t].sum[b];
}
else
{
ss=f[t].num[a-];
s=f[t].num[b]-ss;
tsum=f[t].sum[b]-f[t].sum[a-];
}
if (s>=k)
{
a=l+ss;
b=l+ss+s-;
,l,mid,a,b,k);
}
else
{
//lnum+=s;
int b1=a-l-ss;
-s;
a=mid++b1;
b=mid+b1+b2;
sum+=tsum;
,mid+,r,a,b,k-s);
}
}
int Q;
int x,y;
void slove()
{
build(,,n);
scanf("%d",&Q);
;i<=Q;i++)
{
scanf("%d%d",&x,&y);
x++;
y++;
__int64 sum1=all[y]-all[x-];
//printf("sum1=%I64d\n",sum1);
sum=;
//lnum=0;
//printf("sum=%I64d\n",sum);
-x+;
,,n,x,y,k);
//printf("t=%d\n",t);
lnum=k-;
__int64 ans=-sum+sum1-sum-(__int64 )(y-x+-lnum-lnum)*t;
printf("%I64d\n",ans);
}
}
int main()
{
int T;
;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
all[]=;
;i<=n;i++)
{
scanf("%d",&a[i]);
f[].val[i]=sorted[i]=a[i];
all[i]=all[i-]+a[i];
}
printf("Case #%d:\n",++t);
sort(sorted+,sorted+n+);
slove();
printf("\n");
}
;
}