ppp

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+7;
int n,Q;
ll ans[Maxn];
struct ques{
    int l,id;
};
vector<ques>q[Maxn];
int lst[Maxn];
int a[Maxn];

struct TREE{
    int l,r;
    int val;
	int tag,cnt,add;
	ll sm;
}tree[Maxn<<2];

inline void pushup(int node){
    tree[node].sm=tree[node<<1].sm+tree[node<<1|1].sm;
    tree[node].val=tree[node<<1].val+tree[node<<1|1].val;
}
void buildtree(int node,int l,int r){
	tree[node].l=l,tree[node].r=r;
    if(l==r) return ;
    int mid=l+r>>1;
    buildtree(node<<1,l,mid);
    buildtree(node<<1|1,mid+1,r);
    pushup(node);
}
inline void spread(int node,int vk,int ct,int ad){
    tree[node].tag^=vk;
	tree[node].cnt+=ct;
	tree[node].add+=ad;
	int bc=tree[node].val,th=tree[node].r-tree[node].l+1-tree[node].val;
    if(vk) tree[node].val=th;
    tree[node].sm+=1ll*th*((ct+1)/2);
	tree[node].sm+=1ll*bc*(ct-(ct+1)/2);
	tree[node].sm+=1ll*ad*bc;
}
inline void pushdown(int node){
    spread(node<<1,tree[node].tag,tree[node].cnt,tree[node].add);
    spread(node<<1|1,tree[node].tag,tree[node].cnt,tree[node].add);
    tree[node].tag=0;
	tree[node].cnt=0;
	tree[node].add=0;
}
void modify(int node,int l,int r,int tag,int cnt,int add){
    if(tree[node].l>=l and tree[node].r<=r){
        spread(node,tag,cnt,add);
        return ;
    }
    pushdown(node);
    int mid=tree[node].l+tree[node].r>>1;
    if(l<=mid) modify(node<<1,l,r,tag,cnt,add);
    if(r>mid) modify(node<<1|1,l,r,tag,cnt,add);
    pushup(node);
}
ll query(int node,int l,int r){
    if(tree[node].l>=l and tree[node].r<=r) return tree[node].sm;
    pushdown(node);
    int mid=tree[node].l+tree[node].r>>1;
	ll ret=0;
    if(l<=mid) ret=ret+query(node<<1,l,r);
    if(r>mid) ret=ret+query(node<<1|1,l,r);
    return ret;
}

int main(){
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        q[r].emplace_back((ques){l,i});
    }
    buildtree(1,1,n);

    for(int i=1;i<=n;i++){
        modify(1,lst[a[i]]+1,i,1,1,0);
		if(lst[a[i]]) modify(1,1,lst[a[i]],0,0,1);
		
        for(auto [j,id]:q[i]) ans[id]=query(1,j,i);
        
		// cout<<"modfiy "<<lst[a[i]]+1<<" "<<i<<endl;
		// for(int j=1;j<=n;j++) cout<<"now "<<j<<" "<<query(1,j,j)<<endl;
		lst[a[i]]=i;
    }
    for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);

    return 0;
}
/*
5
2 3 5 1 5
5
2 3
1 1
1 3
2 5
2 4
*/