#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
void init(){ }
const int B = 350;
int n,a[100005],bl[100005],s[100005],t[100005];
ll ans; ll ret[100005];
struct Node{
	int l,r,id;
}q[100005];
void upds(int x, int v){ s[x] += v; ans += 1ll*v*t[x]; }
void updt(int x, int v){ t[x] += v; ans += 1ll*v*s[x]; }

bool operator< (Node A, Node B){
	if(bl[A.l] == bl[B.l]) return A.r<B.r;
	else return bl[A.l] < bl[B.l];
}
void procedure(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read(); bl[i]=(i-1)/B+1;
	}
	int Q=read();
	for(int i=1;i<=Q;i++)
		q[i] = (Node){read(),read(),i};
	sort(q+1, q+Q+1);

	int cl=1, cr=n;
	for(int i=1;i<=Q;i++){
		while(cl<q[i].l) upds(a[cl++], 1);
		while(cl>q[i].l) upds(a[--cl], -1);
		while(cr>q[i].r) updt(a[cr--], 1);
		while(cr<q[i].r) updt(a[++cr], -1);
		ret[q[i].id] = cl*(n-cr+1)-ans;
	}
	for(int i=1;i<=Q;i++) printf("%d\n", ret[i]);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=1;
	init();
	while(T--) procedure();
	return 0;
}