bool cmp(const Query& a,const Query& b)
{
    int al=get(a.l),bl=get(b.l);
    if(al!=bl) return al<bl;
    return a.r<b.r;
}

sort(q,q+m,cmp);
    for(int x=0;x<m;)
    {
        int y=x;
        while(y<m&&get(q[x].l)==get(q[y].l)) y++;
        int right=get(q[x].l)*len+len-1;

        while(x<y&&q[x].r<=right)
        {
            LL res=0;
            int id=q[x].id,l=q[x].l,r=q[x].r;
            for(int i=l;i<=r;i++) add(w[i],res);
            ans[id]=res;
            for(int i=l;i<=r;i++) cnt[w[i]]--;
            x++;
        }
        LL res=0;
        int i=right,j=right+1;
        while(x<y)
        {
            int id=q[x].id,l=q[x].l,r=q[x].r;
            while(i<r) add(w[++i],res);
            LL backup=res;
            while(j>l) add(w[--j],res);
            ans[id]=res;
            while(j<right+1) cnt[w[j++]]--;
            res=backup;
            x++;
        }
        memset(cnt,0,sizeof cnt);
    }