HDU #3333

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N(3e4+5), M(1e5+5);

LL bit[N], ans[M];
int pos[N], a[N], b[N], n, q;

void add(int x, int v)
{
    for(; x<=n; bit[x]+=v, x+=x&-x);
}

LL sum(int x)
{
    LL res=0;
    for(; x; res+=bit[x], x-=x&-x);
    return res;
}

struct P
{
    int l, r, id;
    P(int l, int r, int id):l(l),r(r),id(id){}
    P(){}
    bool operator<(const P &b)const{return r<b.r;}
}p[M];


int main()
{
    int T;
    for(cin>>T; T--; )
    {
        cin>>n;
        for(int i=1; i<=n; i++) cin>>a[i], b[i-1]=a[i];
        sort(b, b+n);   //error-prone
        int *e=unique(b, b+n);
        memset(bit, 0, sizeof(bit));
        memset(pos, 0, sizeof(pos));
        cin>>q;
        for(int l, r, i=0; i<q; i++)
        {
            cin>>l>>r;
            p[i]={l, r, i};
        }
        sort(p, p+q);
        for(int i=0, j=1, k; i<q && j<=n; )
        {
            for(; j<=p[i].r; j++)
            {
                int id=lower_bound(b, e, a[j])-b;
                if(pos[id]) add(pos[id], -a[j]);
                pos[id]=j, add(j, a[j]);
            }
            for(k=i; p[k].r==p[i].r; k++)
            {
                ans[p[k].id]=sum(p[k].r)-sum(p[k].l-1);
            }
            i=k;
        }
        for(int i=0; i<q; i++) cout<<ans[i]<<endl;
    }
    return 0;
}