#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif

const int max_n = 2e5+10;

const int max_log=31;

const long long inf = 4000111222000111222LL;

/*struct Line {
    long double k, b;
    Line(long double k, long double b): k(k), b(b) {
    }
    long double get_value(long double x) const {
        return k * x + b;
    }
    bool operator < (const Line &l) const {
        return k > l.k || (k == l.k && b < l.b);
    }
};
long double intersection(const Line &l1, const Line &l2) {
    return (l2.b - l1.b) / (l1.k - l2.k);
}*/

struct Line {
    long long k, b;

    Line(long long k = 0, long long b = 0): k(k), b(b) {
    }

    long long get_value(long long x) const {
        return k * x + b;
    }

    bool operator < (const Line &l) const {
        return k > l.k || (k == l.k && b < l.b);
    }
};

long long intersection(const Line &l1, const Line &l2) {
    long long a = l2.b - l1.b;
    long long b = l1.k - l2.k;
    return a / b - ((a ^ b) < 0 && a % b);
}

template<int x_increase>
class LineContainer {
public:
    LineContainer(): pos(0) {
    }

    void clear() {
        pos = 0;
//        last_x = (x_increase == 1 ? numeric_limits<long long>::min() : numeric_limits<long long>::max());
        v.clear();
    }

    void add(const Line &l) {
        if (!v.empty()){
            assert(v.back().k >= l.k);
            if (v.back().k == l.k) {
                if (l.b >= v.back().b) {
                    return;
                }
                v.pop_back();
            }
            while (v.size() >= 2 && intersection(v[v.size() - 2], v.back()) >= intersection(v.back(), l)) {
                v.pop_back();
            }
        }
        v.push_back(l);
    }

    long long get_min(long long x) {
        if (v.empty()) {
            return inf;
        }
        if (x_increase == 1) {
//            assert(last_x <= x);
//            last_x = x;
            pos = min(pos, v.size() - 1);
            while (pos + 1 < v.size() && v[pos].get_value(x) > v[pos + 1].get_value(x)) {
                ++pos;
            }
            return v[pos].get_value(x);
        } else if (x_increase == -1) {
//            assert(last_x >= x);
//            last_x = x;
            while (v.size() >= 2 && v.back().get_value(x) > v[v.size() - 2].get_value(x)) {
                v.pop_back();
            }
            return v.back().get_value(x);
        } else {
            int l = -1, r = v.size() - 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                if (x <= intersection(v[mid], v[mid + 1])) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            return v[r].get_value(x);
        }
    }

    size_t pos;
//    long long last_x;
    vector<Line> v;
};

namespace fastio {

    const int buf_size = 1 << 14, small = 30;
    char buf_read[buf_size + small];
    char buf_write[buf_size + small];
    char *ptr_read = buf_read + buf_size;
    char *ptr_write = buf_write;

    long long read_int() {
#if __APPLE__
        ll x;
        cin>>x;
        return x;
#endif
        auto getChar = []() {
            if (ptr_read == buf_read + buf_size){
                buf_read[fread(buf_read, 1, buf_size, stdin)] = 0;
                ptr_read = buf_read;
            }
            return *ptr_read++;
        };
        char c = getChar();
        while (c && (c < '0' || c > '9') && c != '-') {
            c = getChar();
        }
        long long z = 1;
        if (c == '-') {
            z = -1;
            c = getChar();
        }
        long long res = 0;
        while (c >= '0' && c <= '9'){
            res = res * 10 + (c - '0');
            c = getChar();
        }
        return z * res;
    }

    void write_flush() {
        fwrite(buf_write, 1, ptr_write - buf_write, stdout);
        ptr_write = buf_write;
    }

    void write_int(long long x) {
        if (x < 0) {
            *ptr_write++ = '-';
            x = -x;
        }
        char *start = ptr_write;
        if (!x) {
            *ptr_write++ = '0';
        }
        while (x) {
            *ptr_write++ = x % 10 + '0';
            x /= 10;
        }
        reverse(start, ptr_write);
        if (ptr_write >= buf_write + buf_size) {
            write_flush();
        }
    }

    void write_char(char c) {
        *ptr_write++ = c;
        if (ptr_write >= buf_write + buf_size) {
            write_flush();
        }
    }

}

LineContainer<0> lc0;
LineContainer<+1> lc1;

int n,m;
ll pref[max_n];

int l[max_n];
int r[max_n];

int L[max_n];
int R[max_n];
int M[max_n];
int ans[max_n];

bool solved_req[max_n];
ll mn[max_n];

LineContainer<+1> lc1_tree[2*max_n];
//vector<int> req_vh[4*max_n];

//vector<int> on_left;
//vector<int> on_right_partially;
//vector<int> on_right_fully;
//
//void solve_mn_fast(int l1,int r1,vector<int> req)
//{
//    if (l1==r1){
//        for (auto i:req){
//            mn[i]=min(mn[i],pref[l1]-1ll*l1*M[i]);
//        }
//        return;
//    }
//    int m1=(l1+r1)/2;
//    vector<int> req_l;
//    vector<int> req_r;
//    on_left.clear();
//    on_right_partially.clear();
//    on_right_fully.clear();
//    for (auto i:req){
//        if (r[i]<=m1){
//            req_l.pb(i);
//        }
//        else if (l[i]>=m1+1){
//            req_r.pb(i);
//        }
//        else{
//            req_l.pb(i);
//            if (r[i]<r1){
//                on_right_partially.pb(i);
//            }
//            else{
//                on_right_fully.pb(i);
//            }
//        }
//    }
//    sort(all(on_right_partially),[&](const int& lhs,const int &rhs){
//        return r[lhs]>r[rhs];
//    });
//    {
//        lc0.clear();
//        for (int j=m1+1;j<=r1;j++){
//            lc0.add(Line(-j,pref[j]));
//            while (!on_right_partially.empty() && r[on_right_partially.back()]==j){
//                int id=on_right_partially.back();
//                on_right_partially.pop_back();
//                mn[id]=min(mn[id],lc0.get_min(M[id]));
//            }
//        }
//        assert(on_right_partially.empty());
//    }
//    {
//        lc1.clear();
//        for (int j=m1+1;j<=r1;j++){
//            lc1.add(Line(-j,pref[j]));
//        }
//        for (auto i:on_right_fully){
//            mn[i]=min(mn[i],lc1.get_min(M[i]));
//        }
//    }
//    solve_mn_fast(l1,m1,req_l);
//    solve_mn_fast(m1+1,r1,req_r);
//}

void build(int v,int l,int r)
{
    lc1_tree[v].v.reserve(r-l+1);
    for (int i=l;i<=r;i++){
        lc1_tree[v].add(Line(-i,pref[i]));
    }
    if (l==r){
        return;
    }
    int m=(l+r)/2;
    build(v+1,l,m);
    build(v+2*(m-l+1),m+1,r);
}

//void push_req(int v,int l,int r,int tl,int tr,int id)
//{
//    if (l>tr || r<tl){
//        return;
//    }
//    if (l>=tl&&r<=tr){
//        req_vh[v].pb(id);
//        return;
//    }
//    int m=(l+r)/2;
//    push_req(2*v,l,m,tl,tr,id);
//    push_req(2*v+1,m+1,r,tl,tr,id);
//}

vector<int> req_on_deep[20];

void solve_mn_fast2(int v,int l1,int r1,int deep=0)
{
    if (req_on_deep[deep].empty()){
        return;
    }
    if (l1==r1){
        for (auto i:req_on_deep[deep]){
            mn[i]=min(mn[i],pref[l1]-1ll*l1*M[i]);
        }
        return;
    }
    int m1=(l1+r1)/2;
    vector<int> left;
    vector<int> right;
    lc1_tree[v].pos = 0;
//    lc1_tree[v].last_x = numeric_limits<long long>::min();
    req_on_deep[deep+1].clear();
    for (auto i:req_on_deep[deep]){
        if (l[i]<=l1 && r1<=r[i]){
            mn[i]=min(mn[i],lc1_tree[v].get_min(M[i]));
        }
        else{
            if (l[i]<=m1){
                req_on_deep[deep+1].pb(i);
            }
        }
    }
    solve_mn_fast2(v+1,l1,m1,deep+1);
    req_on_deep[deep+1].clear();
    for (auto i:req_on_deep[deep]){
        if (l[i]<=l1 && r1<=r[i]){
//            mn[i]=min(mn[i],lc1_tree[v].get_min(M[i]));
        }
        else{
            if (r[i]>=m1+1){
                req_on_deep[deep+1].pb(i);
            }
        }
    }
    solve_mn_fast2(v+2*(m1-l1+1),m1+1,r1,deep+1);
}

ll sub;

void get_kostya(int v, int tl, int tr, int l, int r,int id) {
    LOG(v,tl,tr,l,r,id);
    if (mn[id]-sub<0) return;
    ll val = lc1_tree[v].get_min(M[id]);
    if (val > mn[id]) return;
    if (tl == l && tr == r) {
        mn[id]=min(mn[id], val);
        return;
    }
    if (val-sub>=0) return;
    if (l <= -lc1_tree[v].v[lc1_tree[v].pos].k && -lc1_tree[v].v[lc1_tree[v].pos].k <= r) {
        mn[id]=min(mn[id], val);
        return;
    }
    int mid = (tl + tr) / 2;
    if (r <= mid) {
        get_kostya(v+1, tl, mid, l, r,id);
        return;
    } else if (l > mid) {
        get_kostya(v + 2*(mid-tl+1), mid + 1, tr, l, r,id);
        return;
    }
    get_kostya(v+1, tl, mid, l, mid,id);
    get_kostya(v+2*(mid-tl+1), mid + 1, tr, mid + 1, r,id);
}

void solve_req(vector<int> req)
{
    LOG("solve_req");
    for (auto i:req){
        solved_req[i]=1;
        mn[i]=1e18;
    }
    // for (auto i:req){
    //     for (int j=l[i];j<=r[i];j++){
    //         mn[i]=min(mn[i],pref[j]-1ll*j*M[i]);
    //     }
    // }
    sort(all(req),[&](const int& lhs,const int &rhs){
        return M[lhs]<M[rhs];
    });
    // req_on_deep[0]=req;
    // solve_mn_fast2(1,0,n-1,0);
    for (int i=0;i<2*max_n;i++){
        lc1_tree[i].pos=0;
    }
    for (auto i:req){
        if (l[i] - 1 >= 0) {
            sub = pref[::l[i] - 1] - 1ll * (::l[i] - 1) * M[i];
        }
        else {
            sub = +M[i];
        }
        get_kostya(1,0,n-1,l[i],r[i],i);
    }
//    solve_mn_fast(0,n-1,req);
//    for (int i=0;i<4*max_n;i++){
//        lc1_tree[i].pos = 0;
//        lc1_tree[i].last_x = numeric_limits<long long>::min();
//        sort(all(req_vh[i]),[&](const int& lhs,const int &rhs){
//            return M[lhs]<M[rhs];
//        });
//        for (auto j:req_vh[i]){
//            mn[j]=min(mn[j],lc1_tree[i].get_min(M[j]));
//        }
//    }
    for (auto i:req){
        LOG(i,M[i],mn[i]);
        if (mn[i]-pref[l[i]-1]+1ll*(l[i]-1)*M[i]<0){
            solved_req[i]=0;
        }
    }
}

/*
i,M[i],mn[i] :: 0 500000005 -3500000002
i,M[i],mn[i] :: 1 500000005 -1499999989
i,M[i],mn[i] :: 2 500000005 -1999999989
i,M[i],mn[i] :: 3 500000005 -2499999996
i,M[i],mn[i] :: 4 500000005 -4000000008

i,M[i],mn[i] :: 0 500000005 -3500000002
i,M[i],mn[i] :: 1 500000005 -1499999989
i,M[i],mn[i] :: 2 500000005 -1999999989
i,M[i],mn[i] :: 3 500000005 -2499999996
i,M[i],mn[i] :: 4 500000005 -4000000008
*/

const bool gen=0;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (gen){
        n=2e5;
        m=2e5;
    }
    else{
        n=fastio::read_int();
        m=fastio::read_int();
    }
    for (int i=0;i<n;i++){
        int a;
        if (gen){
            a=rand()%10000;
        }
        else{
            a=fastio::read_int();
        }
        pref[i] = (i==0 ? 0 : pref[i-1]) + a;
    }
    build(1,0,n-1);
    for (int i=0;i<m;i++){
        if (gen){
            l[i]=rand()%n;
            r[i]=rand()%n;
            if (l[i]>r[i]){
                swap(l[i],r[i]);
            }
        }
        else{
            int s,k;
            s=fastio::read_int();
            k=fastio::read_int();
            l[i]=s-1;
            r[i]=s+k-2;
        }

//        push_req(1,0,n-1,l[i],r[i],i);

        L[i]=-1;
        R[i]=min(pref[l[i]] - (l[i] ? pref[l[i] - 1] : 0ll), (pref[r[i]] - (l[i] ? pref[l[i] - 1] : 0ll)) / (r - l + 1));

    }
    for (int iter=0;iter<max_log;iter++){
        vector<int> req;
        for (int i=0;i<m;i++){
            if (L[i]!=R[i]){
                M[i]=(L[i]+R[i]+1)/2;
                req.pb(i);
            }
        }

        solve_req(req);
        for (int i=0;i<m;i++){
            if (L[i]!=R[i]){
                if (solved_req[i]){
                    L[i]=M[i];
                }
                else{
                    R[i]=M[i]-1;
                }
            }
        }
    }

    for (int i=0;i<m;i++){
        if (L[i]==-1){
            cout<<"stay with parents"<<"\n";
        }
        else{
            cout<<L[i]<<"\n";
        }
    }
}

/*
9 5
6 1 10 9 5 -2 3 1 -1
3 6
1 4
3 3
6 1
8 2
*/