#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5+5;
int n, m, A[N], sum[N];
struct Node{
    int R, id;
    bool operator<(const Node &b)const{return R!=b.R ? R>b.R : id<b.id;}
};
vector<Node> qry[N];
int ans[N];

struct Convh{
    vector<int> stk; int sz=0;

    void add(int id){
        while (sz>1 &&
            (sum[stk[sz-1]]-sum[id])*(stk[sz-2]-stk[sz-1]) >
            (sum[stk[sz-2]]-sum[stk[sz-1]])*(stk[sz-1]-id))
            stk.pop_back(), --sz;
        stk.push_back(id); ++sz;
    } 

    int find(int id){
        int L=0, R=sz-1;
        while (R - L > 20){
            int M1 = L+(R-L)/2, M2 = M1+1;
            int res1 = (sum[stk[M1]]-sum[id])*(stk[M2]-id);
            int res2 = (sum[stk[M2]]-sum[id])*(stk[M1]-id);
            if (res1 == res2) L=R;
            else if (res1 < res2) R = M2;
            else L = M1;
            // std::cerr << "FUCK\n";
        }
        int ans = 0x7f7f7f7f;
        while(L <= R) {
            if(sum[stk[L]]-sum[id] < 0) ans = -1;
            else ans = min(ans, (sum[stk[L]]-sum[id])/(stk[L]-id)), L++;
        }
        if (ans>=0) return ans;
        else return -1;
    }
};

Convh c[N];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; ++i) cin >> A[i], sum[i] = sum[i-1]+A[i];
    for (int i=1; i<=m; ++i){
        int s, k; cin >> s >> k;
        qry[s-1].push_back(Node{s+k-1, i});
    }

    for (int i=0; i<n; ++i) sort(qry[i].begin(), qry[i].end());

    for (int i=n; i>=0; --i){
        for(auto [q, id]: qry[i]) {
            int l = i + 1, r = q + 1, a = 0x7f7f7f7f;
            for(int j = r; j; j -= j&-j) if(c[j].sz) a = std::min(a, c[j].find(l - 1));// std::cerr << "FUCK\n";
            ans[id] = a;
        }
        for(int j = i + 1; j <= n + 1; j += j&-j) c[j].add(i);// std::cerr << "Blyat\n";
    }

    for(int i = 1; i <= m; ++i) {
        if(ans[i] < 0) std::cout << "stay with parents\n";
        else           std::cout << ans[i] << char(10);
    }

    return 0;
}