#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define pq priority_queue
#define il inline
#define rg register
namespace d909RCA_math
{
	int fac[200009];
	void Cinit(int p) 
	{
		fac[0] = 1;
		for(int i=1;i<200000;i++)
		{
			fac[i]=fac[i-1]*i%p;
		}
	}
	int qpow(int a,int b,int p) 
	{
		int ans=1;
		while(b) 
		{
			if(b&1) ans=ans*a%p;
			a=a*a%p;
			b>>=1;
		}
		return ans;
	}
	int C(int n,int m,int p) 
	{
		if(m>n||m<0) return 0;
		return fac[n]*qpow(fac[m],p-2,p)%p*qpow(fac[n-m],p-2,p)%p;
	}
	int Lucas(int n,int m,int p) 
	{
		if(!m) return 1;
		return (C(n%p,m%p,p)*Lucas(n/p,m/p,p))%p;
	}
	int GCD(int n,int m,int p) 
	{
		return __gcd(n,m)%p;
	}
	int LCM(int n,int m,int p) 
	{
		return n*m%p*qpow(GCD(n,m,p),p-2,p)%p;
	}
}
using namespace d909RCA_math;
// #define file 1
// #define multi_test 1
#define segment_tree 1
#ifdef segment_tree
#define mid ((l+r)>>1)
#define mid2 ((t+b)>>1)
#define lson k<<1
#define rson k<<1|1
#define son1 (k<<2)+1
#define son2 (k<<2)+2
#define son3 (k<<2)+3
#define son4 (k<<2)+4
#endif
namespace d909RCA
{
	int n,m,ans[200009],dep[200009],sum[200009],num[50009],a[50009],suf[50009],pre[50009],fa[200009][19];
	vector<pair<int,pair<int,int> > > q[50009];
	int lca(int x,int y)
	{
		x=num[x];
		y=num[y];
		if(dep[x]>dep[y]) swap(x,y);
		while(dep[x]!=dep[y])
		{
			y=fa[y][0];
		}
		// cout<<x<<" "<<y<<'\n';
		for(int i=8;i>=0;i--)
		{
			if(fa[x][i]!=fa[y][i])
			{
				x=fa[x][i];
				y=fa[y][i];
			}
		}
		// cout<<x<<" "<<y<<" "<<fa[x][0]<<" "<<fa[y][0]<<'\n';
		return fa[x][0];
	}
	void build(int k,int l,int r)
	{
		fa[k][0]=k>>1;
		dep[k]=dep[k>>1]+1;
		// cout<<k<<" "<<dep[k]<<'\n';
		if(l==r)
		{
			sum[k]=a[l];
			num[l]=k;
			return ;
		}
		build(lson,l,mid);
		build(rson,mid+1,r);
	}
	void dfs(int k,int l,int r)
	{
		memset(suf,-0x3f,sizeof(suf));
		memset(pre,-0x3f,sizeof(pre));
		// cout<<k<<" "<<l<<" "<<r<<'\n';
		int sum=0;
		for(int i=mid;i>=l;i--)
		{
			sum+=a[i];
			suf[i]=max(suf[i+1],sum);
		}
		sum=0;
		for(int i=mid+1;i<=r;i++)
		{
			sum+=a[i];
			pre[i]=max(pre[i-1],sum);
		}
		if(l==r)
		{
			for(pair<int,pair<int,int> > i:q[k])
			{
				ans[i.first]=max(ans[i.first],a[l]);
				// cout<<i.second.second<<" "<<i.second.first<<'\n';
			}
		}
		else
		{
			for(pair<int,pair<int,int> > i:q[k])
			{
				ans[i.first]=max(ans[i.first],suf[i.second.first]+pre[i.second.second]);
				if(i.second.first<=mid) q[lson].push_back({i.first,{i.second.first,mid}});
				if(i.second.second>mid) q[rson].push_back({i.first,{mid+1,i.second.second}});
				// cout<<i.second.second<<" "<<i.second.first<<'\n';
			}
		}
		if(l==r) return ;
		dfs(lson,l,mid);
		dfs(rson,mid+1,r);
	}
	void inp()
	{
        cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
	}
	void solve()
	{
        build(1,1,n);
		for(int i=1;i<=n*4;i++)
		{
			for(int j=1;j<=8;j++)
			{
				fa[i][j]=fa[fa[i][j-1]][j-1];
			}
		}
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			cin>>x>>y;
			z=lca(x,y);
			q[z].push_back({i,{x,y}});
		}
		memset(ans,-0x3f,sizeof(ans));
		dfs(1,1,n);
	}
	void print()
	{
		for(int i=1;i<=m;i++)
		{
			cout<<ans[i]<<'\n';
		}
	}
}
using namespace d909RCA;
signed main()
{
	int t=1;
	IOS
	#ifdef file
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif
	#ifdef multi_test
		cin>>t;
		ios::sync_with_stdio(true);
	#endif
	while(t--)
	{
		d909RCA::inp();
		d909RCA::solve();
		d909RCA::print();
	}
	return 0;
}