#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <map>

#include <set>

#include <queue>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 1000005

#define inf 0x3f3f3f3f

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

void Finout()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    freopen("wa.txt","w",stdout);

    #endif

}

int Getint()

{

    int 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;

}

const int buf=200005;

int n,m,a[maxn],last[maxn],bac[maxn];

struct Que{int l,r,id,ans;}q[maxn];

struct Segment_Tree{

	int L,R,C;

	int old_mx[maxn],old_lazy[maxn];

	int now_mx[maxn],now_lazy[maxn];

	void init()

	{

		memset(old_mx,0,sizeof old_mx);

		memset(now_mx,0,sizeof now_mx);

		memset(old_lazy,0,sizeof old_lazy);

		memset(now_lazy,0,sizeof now_lazy);

	}

	void update(int o,int l,int r)

	{

		old_mx[o]=max(old_mx[o<<1],old_mx[o<<1|1]);

		now_mx[o]=max(now_mx[o<<1],now_mx[o<<1|1]);

	}

	void pushdown(int o,int l,int r)

	{

		old_lazy[o<<1]=max(old_lazy[o<<1],now_lazy[o<<1]+old_lazy[o]);

		old_lazy[o<<1|1]=max(old_lazy[o<<1|1],now_lazy[o<<1|1]+old_lazy[o]);

		old_mx[o<<1]=max(old_mx[o<<1],now_mx[o<<1]+old_lazy[o]);

		old_mx[o<<1|1]=max(old_mx[o<<1|1],now_mx[o<<1|1]+old_lazy[o]);

		now_lazy[o<<1]+=now_lazy[o];

		now_lazy[o<<1|1]+=now_lazy[o];

		now_mx[o<<1]+=now_lazy[o];

		now_mx[o<<1|1]+=now_lazy[o];

		now_lazy[o]=old_lazy[o]=0;

	}

	void add(int o,int l,int r)

	{

		if (L<=l&&r<=R)

		{

			old_lazy[o]=max(old_lazy[o],now_lazy[o]+=C);

			old_mx[o]=max(old_mx[o],now_mx[o]+=C);

			return ;

		}

		pushdown(o,l,r);

		int mid=l+r>>1;

		if (R<=mid) add(o<<1,l,mid);

		else if (L>mid) add(o<<1|1,mid+1,r);

		else add(o<<1,l,mid),add(o<<1|1,mid+1,r);

		update(o,l,r);

	}

	int query(int o,int l,int r)

	{

		if (L<=l&&r<=R) return old_mx[o];

		pushdown(o,l,r);

		int mid=l+r>>1;

		if (R<=mid) return query(o<<1,l,mid);

		if (L>mid) return query(o<<1|1,mid+1,r);

		else return max(query(o<<1,l,mid),query(o<<1|1,mid+1,r));

	}

}t;

bool cmp1(Que x,Que y){return x.r<y.r;}

bool cmp2(Que x,Que y){return x.id<y.id;}

int main()

{

    Finout();

	n=Getint();

	F(i,1,n) a[i]=Getint();

	F(i,1,n)

	{

		last[i]=bac[a[i]+buf];

		bac[a[i]+buf]=i;

	}

	m=Getint();

	F(i,1,m)

	{

		q[i].l=Getint();

		q[i].r=Getint();

		q[i].id=i;

	}

	sort(q+1,q+m+1,cmp1);

	int h=0;

	F(i,1,m)

	{

		while (h<q[i].r&&h<=n)

		{

			h++;

			t.L=last[h]+1;

			t.R=h;

			t.C=a[h];

//			printf("Add %d %d %d\n",t.L,t.R,t.C);

			t.add(1,1,n);

		}

		t.L=q[i].l;t.R=q[i].r;

//		printf("Query %d %d for %d\n",q[i].l,q[i].r,q[i].id);

		q[i].ans=t.query(1,1,n);

	}

	sort(q+1,q+m+1,cmp2);

	F(i,1,m) printf("%d\n",q[i].ans);

}