Green Line Yan

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 100010;

int n, q;

ll ans[maxn];
ll a[maxn], t[maxn];

int x[maxn];

vector<pair<ll,int>> sweep[maxn];

void calculate()
{
    for(int i = 1 ; i <= q ; i++)
        sweep[ x[i] ].push_back( { t[i] , i } );

    vector<ll> pSum;
    vector<pair<ll,ll>> evTimes;

    for(int i = 1 ; i <= n ; i++)
    {
        if( a[i - 1] > a[i] )
        {
            ll lT = 1, rT = a[i - 1] - a[i];

            while( !evTimes.empty() )
            {
                auto [lLast, rLast] = evTimes.back();
                lLast += i - 1; rLast += i - 1;

                if( rT + 1 <= lLast )
                    break;

                rT += rLast - lLast + 1;

                pSum.pop_back();
                evTimes.pop_back();
            }

            evTimes.emplace_back( lT - i , rT - i );

            if( pSum.empty() )
                pSum.push_back( rT - lT + 1 );
            else
                pSum.push_back( pSum.back() + rT - lT + 1 );
        }
        else
        {
            ll s = a[i - 1];

            while( !evTimes.empty() )
            {
                auto [lLast, rLast] = evTimes.back();
                lLast += i - 1; rLast += i - 1;
                ll diff = rLast - lLast + 1;

                if( s + diff > a[i] )
                {
                    evTimes.back().first += a[i] - s;
                    pSum.back() -= a[i] - s;
                    break;
                }

                s += diff;

                pSum.pop_back();
                evTimes.pop_back();
            }
        }

        while( !sweep[i].empty() )
        {
            auto [cT, id] = sweep[i].back();
            sweep[i].pop_back();

            if( cT == 0 || evTimes.empty() )
            {
                ans[id] = max( ans[id] , a[i] );
                continue;
            }

            if( evTimes[0].second + i <= cT )
            {
                ans[id] = max( ans[id] , a[i] + pSum.back() );
                continue;
            }

            int l = 0, r = (int)evTimes.size() - 1;

            while( l < r )
            {
                int mid = ( l + r )/2;
                if( l == r - 1 ) mid = r;

                if( evTimes[mid].second + i > cT )
                    l = mid;
                else
                    r = mid - 1;
            }

            ll curAns;

            if( cT < evTimes[l].first + i )
                curAns = pSum.back() - pSum[l];
            else
                curAns = pSum.back() - pSum[l] + ( cT - evTimes[l].first - i + 1 );

            ans[id] = max( ans[id] , a[i] + curAns );
        }
    }
}

int main()
{
    scanf("%d %d",&n,&q);

    for(int i = 1 ; i <= n ; i++)
        scanf("%lld",&a[i]);

    for(int i = 1 ; i <= q ; i++)
        scanf("%d %lld",&x[i],&t[i]);

    calculate();

    reverse( a + 1 , a + n + 1 );

    for(int i = 1 ; i <= q ; i++)
        x[i] = n - x[i] + 1;

    calculate();

    for(int i = 1 ; i <= q ; i++)
        printf("%lld\n",ans[i]);
}