#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2) 
#define LL long long
#define LD long double
#define DB double
#define UI unsigned int
#define N 200005
void cmax(int& a,int b){
	(a<b)&&(a=b);
}
void cmin(int& a,int b){
	(a>b)&&(a=b);
}
void Read(int& a){
	char c=a=0;
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')a=(a*10)+(c^'0'),c=getchar();
}
void cmin(LL& a,LL b){
	a>b&&(a=b);
}
bool Bar;
int n,m,l,r,mid,ans,Ans[N],Lim[N];
int top,A[N],s,e,Len[N],len;
LL sum,a,b,Sum[N],Pre[N];
vector<int>St[N],Ed[N];
struct V{
	LL x,y;
}Sk[N],tmp;
bool Ka;//real,imag
int Check(V a,V b,V c){
	return (a.y-b.y)*(c.x-b.x)<(c.y-b.y)*(a.x-b.x);
}
LL Get_b(int p,int k){
	return Sk[p].y-1ll*Sk[p].x*k;
}
LL Check(int k){
	int l=1,r=top-1,mid;
	LL res=Get_b(top,k);
//	printf("res:%lld %lld %lld\n",res+sum,Sk[top].x,Sk[top].y+sum);
	while(l<=r){
		mid=(l+r)>>1;
		if(Sk[mid].x>len){
			l=mid+1;
//			cerr<<"?"<<endl;
			continue;
		}
		a=Get_b(mid,k);
		b=Get_b(mid+1,k);
		cmin(res,a);
		cmin(res,b);
		if(b<=a)l=mid+1;
		else r=mid-1;
	}
	return res;
 }
int main() {
//	printf("%lf\n",(&Ka-&Bar)/1024.0/1024.0);
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&A[i]),Sum[i]=A[i]+Sum[i-1];
	for(int i=1;i<=m;++i){
		scanf("%d %d",&s,&Len[i]);
		e=s+Len[i]-1;
		St[s].push_back(i);
		Ed[n-e+1].push_back(i);
	}
	for(int i=n;i;--i){
		tmp=(V)<%i,-sum%>;
		while(top>1&&Check(tmp,Sk[top],Sk[top-1]))--top;
		Sk[++top]=tmp,sum+=A[i];
//		cerr<<top<<" "<<Sk[top].x<<" "<<Sk[top].y<<endl;
		for(int j:St[i]){
			len=Len[j]+i-1,ans=-1;
			l=0,r=1e9;
			while(l<=r){
				mid=(l+r)>>1;
				Pre[j]=Sum[len-1]-Sum[i-1];
				if(Check(mid)+sum+1ll*mid*(Lim[j]=i-1)>=0)ans=mid,l=mid+1;
				else r=mid-1;
			}
			Ans[j]=ans;
		}
	}
	top=0,sum=0;
	for(int l=1,r=n;l<r;++l,--r)swap(A[l],A[r]);
	for(int i=n;i;--i){
		tmp=(V)<%i-n-1,-sum%>;
		while(top>1&&Check(tmp,Sk[top],Sk[top-1]))--top;
		Sk[++top]=tmp,sum+=A[i];
		for(int j:Ed[i]){
			len=Len[j]+i-1-n-1,ans=-1;
			l=0,r=1e9;
//			cerr<<"Len:"<<len<<" "<<Sk[top].y+sum+Pre[j]+Sk[top].x*3<<endl;
//			exit(0);
			while(l<=r){
				mid=(l+r)>>1;
				if(Check(-mid)+sum+Pre[j]+1ll*mid*Lim[j]>=0)ans=mid,l=mid+1;
				else r=mid-1;
			}
			cmin(Ans[j],ans);
		}
	}
	for(int i=1;i<=m;++i){
		if(Ans[i]==-1)puts("stay with parents");
		else printf("%d\n",Ans[i]);
	}
	
	return 0;
}