#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const int B=320;
int a[MAXN],l[MAXN],r[MAXN],idx[MAXN];
int cntl[MAXN],cntr[MAXN];
ll res[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
        scanf("%d%d",&l[i],&r[i]),idx[i]=i;
    sort(idx+1,idx+q+1,[](int x,int y){
        int xb=l[x]/B,yb=l[y]/B;
        return (xb==yb ? (xb&1 ? r[x]>r[y] : r[x]<r[y]) : xb<yb);
    });
    int cl=1,cr=n;
    ll now=0;
    for(int ii=1;ii<=q;ii++)
    {
        int i=idx[ii];
        while(cl>l[i])cl--,cntl[a[cl]]--,now-=cntr[a[cl]];
        while(cr<r[i])cr++,cntr[a[cr]]--,now-=cntl[a[cr]];
        while(cl<l[i])now+=cntr[a[cl]],cntl[a[cl]]++,cl++;
        while(cr>r[i])now+=cntl[a[cr]],cntr[a[cr]]++,cr--;
        res[i]=1LL*l[i]*(n-r[i]+1)-now;
    }
    for(int i=1;i<=q;i++)
        printf("%lld\n",res[i]);
    return 0;
}