#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<int,int> pii;

int mod=1000000+7;
const double dmod=(double)1/mod;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=2e5+10;

ll p[maxn],a[maxn],inf=1e18;
int n,q;

struct line{
    ll a,b;
    ll eval(ll x){
        return a*x+b;
    }
};
vector<line> tree[maxn*4];
ll intersect(line c1,line c2){
    ll sgn1=(c2.b-c1.b);
    ll sgn2=(c1.a-c2.a);
    if(sgn1>0)sgn1=1;
    else if(sgn1==0)sgn1=0;
    else if(sgn1<0)sgn1=-1;
    if(sgn2>0)sgn2=1;
    else if(sgn2==0)sgn2=0;
    else if(sgn2<0)sgn2=-1;
    if(sgn1*sgn2<0)return -1;
    return (c2.b-c1.b)/(c1.a-c2.a);
}


void append(vector<line>&v,line c){
    //while(v.size() && intersect(v.back(),c)<0)v.pop_back();
    while(v.size()>=2 && intersect(v[v.size()-2],v[v.size()-1])>intersect(v[v.size()-2],c))v.pop_back();
    v.pb(c);
}
void build(int x,int l,int r){

    for(int i=l;i<=r;i++){
        line c;
        c.a=-i;
        c.b=p[i];
        append(tree[x],c);
    }

    if(l==r)return;

    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);

}
ll go(vector<line>&v,ll x){

    int l=0;
    int r=v.size()-1;
    int sr,ret=-1;
    while(l<=r){
        sr=(l+r)/2;

        ll inter=inf;
        if(sr<v.size()-1)inter=intersect(v[sr],v[sr+1]);

        if(x<=inter){
            r=sr-1;
            ret=sr;
        }
        else l=sr+1;

    }

    return v[ret].eval(x);
}
ll qry(int x,int l,int r,int lp,int rp,ll val){

    if(l>rp || r<lp)return inf;
    if(l>=lp && r<=rp){
        return go(tree[x],val);
    }
    int mid=(l+r)/2;
    return min(qry(x*2,l,mid,lp,rp,val),qry(x*2+1,mid+1,r,lp,rp,val));
}

int main() {


    //freopen("test.txt","r",stdin);
    //freopen("moj.txt","w",stdout);

    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        p[i]=p[i-1]+a[i];
    }

    build(1,1,n);

    while(q--){

        int lp,rp;
        scanf("%d %d",&lp,&rp);

        rp=lp+rp-1;

        ll l=0;
        ll r=1e9;
        ll x=-1;
        ll sr;
        while(l<=r){
            sr=(l+r)/2;

            ll pom=qry(1,1,n,lp,rp,sr);

            if(pom-p[lp-1]+(lp-1)*sr>=0){
                l=sr+1;
                x=sr;
            }
            else r=sr-1;

        }

        if(x<0)printf("stay with parents\n");
        else printf("%lld\n",x);

    }


    return 0;
}