#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define Misaka16172 sb
#define kamisako femboy

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using uint = unsigned int;

constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ull mod1 = 1e9+7,mod9 = 998244353;

using namespace std;

template <class T>
inline void read(T &x){
    x = 0;T w = 1;
    char c = 0;
    while(!isdigit(c)){
        if(c=='-')  w = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = ((x<<3)+(x<<1))+c-'0';
        c = getchar();
    }
    x = x*w;
}
template<class T,typename ...Args>
inline void read(T &x,Args &...rest){read(x);read(rest...);}

template<class T>
inline void write(T x){
    if(!x)  return putchar('0'),void();
    else if(x<0) putchar('-'),x*=-1;
    int st[40],t = 0;
    while(x){st[++t] = x%10,x/=10;}
    while(t){putchar(st[t--]+'0');}
}

template <class T>
inline string bin(T x,int d = 0){return (((d>1)||(x>>1))?bin(x>>1,d-1):"")+to_string(x&1);}

int Test = 1,Case = 1;

constexpr int N = 5e5+5;

template<int X,int Y>
struct mat{
	ll a[X][Y];
	mat(){}
	mat(int val){
		for(int y=0;y<Y;y++){
			for(int x=0;x<X;x++)	a[x][y] = val;
		}
	}
	mat(vector<vector<ll>> _a){
		for(int y=0;y<Y;y++){
			for(int x=0;x<X;x++)	a[x][y] = _a[x][y];
		}
	}
	template<int _X,int _Y>
	inline bool operator ==(const mat<_X,_Y> &m)const{
		if(X!=_X || Y!=_Y)	return 0;
		for(int y=0;y<Y;y++){
			for(int x=0;x<X;x++)	if(a[x][y]!=m.a[x][y])	return 0;
		}
		return 1;
	}
	template<int _X,int _Y>
	inline bool operator !=(const mat<_X,_Y> &m)const{return !(*this==m);}
	template<int _X,int _Y>
	inline mat<_X,Y> operator *(const mat<_X,_Y> &m)const{
		mat<_X,Y> res;
		for(int y=0;y<Y;y++){
			for(int x=0;x<_X;x++){
				res.a[x][y] = 0;
				for(int i=0;i<X;i++)	res.a[x][y]+=m.a[x][i]*a[i][y];
			}
		}
		return res;
	}
	inline mat<X,Y> operator +(const mat<X,Y> &m)const{
		mat<X,Y> res;
		for(int y=0;y<Y;y++){
			for(int x=0;x<X;x++)	res.a[x][y] = a[x][y]+m.a[x][y];
		}
		return res;
	}
	template<int x,int y>
	inline ll get(){return a[x-1][y-1];}
	template<int x,int y>
	inline void upd(ll v){a[x-1][y-1] = v;}
};

const mat<3,3> de = mat<3,3>({{1,0,0},{0,1,0},{0,0,1}});

int n,a[N];

struct node{
	mat<1,3> v;
	mat<3,3> t;
};

struct SGT{
	node tr[N<<2];
	inline void up(int p){tr[p].v = tr[p<<1].v+tr[p<<1|1].v;}
	inline void down(int p){
		if(tr[p].t!=de){
			tr[p<<1].t = tr[p].t*tr[p<<1].t,tr[p<<1|1].t = tr[p].t*tr[p<<1|1].t;
			tr[p<<1].v = tr[p].t*tr[p<<1].v,tr[p<<1|1].v = tr[p].t*tr[p<<1|1].v;
			tr[p].t = de;
		}
	}
	void build(int l,int r,int p){
		tr[p].t = de;
		if(l==r)	tr[p].v = mat<1,3>({{0,0,1}});
		else{
			int mid = (l+r)>>1;
			build(l,mid,p<<1),build(mid+1,r,p<<1|1);
			up(p);
		}
	}
	void mul(int l,int r,int nl,int nr,int p,mat<3,3> v){
		if(nl^nr)	down(p);
		if(nl>=l && nr<=r){
			tr[p].v = v*tr[p].v;
			if(nl^nr)	tr[p].t = v*tr[p].t;
		}
		else{
			int mid = (nl+nr)>>1;
			if(mid>=l)	mul(l,r,nl,mid,p<<1,v);
			if(mid+1<=r)	mul(l,r,mid+1,nr,p<<1|1,v);
			up(p);
		}
	}
	ll query(int l,int r,int nl,int nr,int p,int t){
		if(nl^nr)	down(p);
		if(nl>=l && nr<=r)	return tr[p].v.get<1,1>()*t+tr[p].v.get<1,2>();
		else{
			int mid = (nl+nr)>>1;
			ll res = 0;
			if(mid>=l)	res+=query(l,r,nl,mid,p<<1,t);
			if(mid+1<=r)	res+=query(l,r,mid+1,nr,p<<1|1,t);
			return res;	
		}
	}
}sgt;

struct Query{
	int l,r,id;
	inline bool operator <(const Query &q)const{return r<q.r;}
}Q[N];

int q,lst[N],ans[N];

void solve(){
    read(n);
    for(int i=1;i<=n;i++)	read(a[i]);
    read(q);
	for(int i=1;i<=q;i++)	read(Q[i].l,Q[i].r),Q[i].id = i;
	sort(Q+1,Q+1+q);
	int p = 1;
	sgt.build(1,n,1);
	for(int r=1;r<=n;r++){
		mat<3,3> d = mat<3,3>({{-1,2*(r-1),0},{0,1,0},{1,-(r-1),1}});
		sgt.mul(lst[a[r]]+1,r,1,n,1,d);
		lst[a[r]] = r;
		while(p<=q && Q[p].r==r){
			ans[Q[p].id] = sgt.query(Q[p].l,r,1,n,1,r);
			p++;
		}
	}
	for(int i=1;i<=q;i++)	cout<<ans[i]<<"\n";
}

int main(){
//  read(Test);
    for(;Case<=Test;++Case) solve();
    return 0;
}