/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author majk
 */

#ifndef MAJK_LIB
#define MAJK_LIB

#include <vector>
#include <stack>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <array>
#include <bitset>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
ui logceil(ll x) { return x?8*sizeof(ll)-__builtin_clzll(x):0; }

namespace std { template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}}; }
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename F> double bshd(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){l=m;}else{h=m;}}return (l+h)/2;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename F> double bsld(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){h=m;}else{l=m;}}return (l+h)/2;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }


template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template<typename T>class vector3:public vector<vector2<T>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector2<T>>(a,vector2<T>(b,c,t)){}};
template<typename T>class vector4:public vector<vector3<T>>{public:vector4(){} vector4(size_t a,size_t b,size_t c,size_t d,T t=T()):vector<vector3<T>>(a,vector3<T>(b,c,d,t)){}};
template<typename T>class vector5:public vector<vector4<T>>{public:vector5(){} vector5(size_t a,size_t b,size_t c,size_t d,size_t e,T t=T()):vector<vector4<T>>(a,vector4<T>(b,c,d,e,t)){}};


#endif
#ifndef MAJK_ENVELOPE_H
#define MAJK_ENVELOPE_H

#ifndef MAJK_INT128_H
#define MAJK_INT128_H


/** Product of two 64-bit numbers modulo another. */
ull mulull(ull a, ull z, ull mod) {
#ifdef __SIZEOF_INT128__
    __int128 result = ((__int128) a * (__int128) z) % (__int128) mod;
    return (ull) result;
#else
    // schrage method
	ull q = mod / a, r = mod % a;
	ull rzq = (r < q) ? r * (z/q) : mulull(r, z/q, mod);
	ull azq = a * (z % q);
	if (azq >= rzq) return azq-rzq; else return azq-rzq+mod;
#endif
}

/** Multiply two 64-bit unsigned integers to get a 128-bit unsigned integer (as a pair of ull) */
pair<ull,ull> mulull(ull a, ull b) {
#ifdef __SIZEOF_INT128__
    __int128 result = (__int128) a * (__int128) b;
    return {(ull) (result >> 64), (ull) result};
#else
    ull c = (ui)a, d = a>>32, e = (ui)b, f = b>>32, g = d*f, h = d*e, i = f*c, j = c*e, k = (j>>32)+(ui)h+(ui)i, left = g+(h>>32)+(i>>32)+(k>>32);
	return {left, ((h+i) << 32) + j};
#endif
}


bool fractionGreaterOrEqual(ll a, ll b, ll c, ll d) {
    if (b < 0) { b = -b; a = -a; }
    if (d < 0) { d = -d; c = -c; }
    return a < 0 && c < 0 ? mulull(-a, d) <= mulull(-c, b) : (a >= 0) && (c < 0 || mulull(a, d) >= mulull(c, b));
}

bool fractionGreaterOrEqual(pair<ll, ll> a, pair<ll, ll> b) {
    return fractionGreaterOrEqual(a.x, a.y, b.x, b.y);
}


bool fractionGreaterOrEqual(double a, double b, double c, double d) {
    return a/b >= c/d;
}

// this is based on modulus, but it's 2-3 times slower than the former
//bool fractionGreaterOrEqual(ll a, ll b, ll c, ll d) {
//	if (a<0 && c<0) return greaterOrEqual(-c,d,-a,b);
//	if (a<0) return false;
//	if (c<0) return true;
//	if (b==0) return true;
//	if (d==0) return false;
//	ll ab = a/b, cd = c/d;
//	if (ab > cd) return true;
//	if (ab < cd) return false;
//	return !greaterOrEqual(b, a%b, d, c%d);
//}

#endif //MAJK_INT128_H


/** Computing lower and upper envelope. Useful for "convex hull trick". */
namespace Envelope {
    template<typename T>
    struct Line {
        T m, b; int id;
        mutable function<const Line<T> *()> succ;

        bool operator<(const Line &rhs) const {
            if (rhs.b != numeric_limits<T>::min()) return m < rhs.m;
            const Line *s = succ();
            if (!s) return 0;
            return b - s->b < (s->m - m) * rhs.m;
        }
    };

    template<typename T>
    struct Upper : public multiset<Envelope::Line<T>> {
        using parent = multiset<Line<T>>;

        bool bad(typename parent::iterator y) {
            auto z = next(y);
            if (y == parent::begin()) {
                return z != parent::end() && y->m == z->m && y->b <= z->b;
            } else {
                auto x = prev(y);
                if (z == parent::end()) {
                    return y->m == x->m && y->b <= x->b;
                } else {
                    return fractionGreaterOrEqual(x->b - y->b, y->m - x->m, y->b - z->b, z->m - y->m);
                }
            }
        }

        void insert_line(T m, T b, int i = 0) {
            auto y = parent::insert({m, b, i});
            y->succ = [=] { return next(y) == parent::end() ? 0 : &*next(y); };
            if (bad(y)) { parent::erase(y); return; }
            while (next(y) != parent::end() && bad(next(y))) parent::erase(next(y));
            while (y != parent::begin() && bad(prev(y))) parent::erase(prev(y));
        }

        T operator[](T x) const {
            auto l = parent::lower_bound({x, numeric_limits<T>::min()});
            return l == parent::end() ? numeric_limits<T>::min() : l->m * x + l->b;
        }

        int best(T x) const {
            auto l = parent::lower_bound({x, numeric_limits<T>::min()});
            return l == parent::end() ? -1 : l->id;
        }

        pair<int, T> bestIndexed(T x) const {
            auto l = parent::lower_bound({x, numeric_limits<T>::min()});
            return (l == parent::end()) ? pair<int, T>{-1, T(0)} : pair<int, T>{l->id, l->m * x + l->b};
        }
    };

    // Lower envelope. WARNING: the internal representation changes m & b.
    template<typename T>
    struct Lower : public Upper<T> {
        void insert_line(T m, T b, int i = 0) { Upper<T>::insert_line(-m, -b, i); }
        T operator[](T x) const { return -Upper<T>::operator[](x); }
    };
}

/* UpperEnvelope that with O(N) build and amortized O(1) query.
 * The updates need be sorted by (m,b), the queries need to be sorted by x, and
 * updates need to come before queries. */
namespace LinearEnvelope {
    template<typename T> struct Line { T m, b; int id; };

    template <typename T>
    struct Upper : public vector<Line<T>> {
        using parent = vector<Line<T>>;
        using parent::at; using parent::back; using parent::size;

        T t; int i;

        Upper() : t(0), i(0) {}

        void clear() {
            parent::clear();
            i = 0;
            t = 0;
        }

        void insert_line(T m, T b, int i = 0) {
            assert(t == 0);
            if (size() > 0 && back().m == m && back().b >= b) return;
            while (size() > 0 && ((back().b < b) || (back().b == b && back().m < m))) parent::pop_back();
            while (size() >= 2 && fractionGreaterOrEqual(at(size()-2).b - back().b, back().m - at(size()-2).m, back().b - b, m - back().m)) parent::pop_back();
            parent::push_back({m,b,i});
        }

        pair<T,int> advance(T x) {
            assert(x >= 0);
            t += x;
            while (i+1 < size() && at(i).m * t + at(i).b < at(i+1).m * t + at(i+1).b) ++i;
            return {at(i).m * t + at(i).b, at(i).id};
        }
    };};


#endif //MAJK_ENVELOPE_H



template<typename F>struct NoOp{void setup(ui, F){}void op(F&p,F n,ui,ui){p=n;}void down(F&,F&,F&,ui,ui) {}};

template<typename F,typename SetOp,typename PowerOp>struct Lazy{
    void setup(ui s,F def){this->def=def;this->s=s;L=new F[s]();fill(L,L+s,def);}
    void down(F&u,F&l,F&r,ui i,ui s){op(l,L[i],i<<1,s>>1);op(r,L[i],i<<1|1,s>>1);L[i]=def;}
    void op(F&p,F n,ui i,ui s){p=sop(p,pop(n,s));if(i<this->s)this->L[i]=sop(this->L[i],n);}
    SetOp sop;PowerOp pop;F*L;ui s;F def;
};

template <typename F, typename CombineOp, typename ModifyOp = NoOp<F>> struct SegTree {
	void setup(ui s, F def) {
		n = 1<<logceil(s);
		T = vector<F>(2*n, def);
		for (ui i = n-1; i > 0; i--) T[i] = cop(T[i<<1],T[i<<1|1]);
		mop.setup(2*n,def);
	}

	void setup(vector<F> & data, F def = F(), F def2 = F()) {
		n = 1<<logceil(data.size());
		T = vector<F>(2*n, def);
		copy(data.begin(), data.end(), T.begin() + n);
		for (ui i = n-1; i > 0; i--) T[i] = cop(T[i<<1],T[i<<1|1]);
		mop.setup(2*n,def2);
	}

	inline void put(ui x, F n) { put(x, x, n); }
	inline void put(ui from, ui to, F v) { put2(from, to+1, v, 1, n); }
	inline F get(ui x) { return get(x, x); }
	inline F get(ui from, ui to) { return get2(from, to+1, 1, n); }

	void put2(ui from, ui to, F v, ui i, ui s) {
		if (from == 0 && to == s) { mop.op(T[i], v, i, s); return; }
		mop.down(T[i], T[i<<1], T[i<<1|1], i, s);
        s>>=1;i<<=1;
        if (to <= s) { put2(from, to, v, i, s); }
        else if (from >= s) { put2(from-s, to-s, v, i|1, s); }
        else {
            put2(from, s, v, i, s);
            put2(0, to-s, v, i|1, s);
        }
		T[i>>1] = cop(T[i], T[i|1]);
	}

	F get2(ui from, ui to, ui i, ui s) {
        while (true) {
            if (from == 0 && to == s) return T[i];
            mop.down(T[i], T[i << 1], T[i << 1 | 1], i, s);
            s >>= 1;i <<= 1;
            if (to > s) {
                to -= s;
                if (from >= s) { from -= s; i|=1; }
                else return cop(get2(from, s, i, s), get2(0, to, i|1, s));
            }
        }
    }

	ui n;
	vector<F> T;
	CombineOp cop;
    ModifyOp mop;
};


template <typename F> struct AddOp { F operator()(F a, F b) { return a+b; }};
template <typename F> struct MinOp { F operator()(F a, F b) { return std::min(a,b); }};
template <typename F> struct MaxOp { F operator()(F a, F b) { return std::max(a,b); }};
template <typename F> struct MultiplyOp { F operator()(F a, F b) { return a*b; }};
template <typename F> struct MultOp { F operator()(F a, ui b) { return a*b; }};
template <typename F> struct IdempOp { F operator()(F a, ui b) { return a; }};
template <typename F> struct InverseOp { F operator()(F a, F b) { return b?b-a:a; }};

template<typename T> using AddSumTree = SegTree<T, AddOp<T>, Lazy<T, AddOp<T>, MultOp<T>>>;
template<typename T> using AddMaxTree = SegTree<T, MaxOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
template<typename T> using AddMinTree = SegTree<T, MinOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
// NOTE: set defaultValue properly in these (-INF for MAX and INF for MIN), otherwise you'll get weird results
template<typename T> using AssignMinTree = SegTree<T, MinOp<T>, Lazy<T, MinOp<T>, IdempOp<T>>>;
template<typename T> using AssignMaxTree = SegTree<T, MaxOp<T>, Lazy<T, MaxOp<T>, IdempOp<T>>>;
template<typename T> using XorTree = SegTree<T, AddOp<T>, Lazy<T, InverseOp<T>, MultOp<T>>>;

template<typename T> using SetMinTree = SegTree<T, MinOp<T>>;
template<typename T> using SetMaxTree = SegTree<T, MaxOp<T>>;
template<typename T> using SetMulTree = SegTree<T, MultiplyOp<T>>;


class FContestWithDrinksHard {
public:
    void solve(istream& cin, ostream& cout) {
        int N; cin >> N;
        vector<int> T(N); cin >> T;
        int M; cin >> M;
        vector<pii> P(M); cin >> P;

        vector2<ll> DP(2, N+1, 0);
        vector2<vector<ll>> Fragments(2, N);

        for (int t = 0; t < 2; ++t) {
            vector<ll> Pref(N + 1, 0);
            for (int i = 0; i < N; ++i) Pref[i + 1] = Pref[i] + T[i];
            Envelope::Upper<ll> Env;
            for (ll i = 0; i < N; ++i) {
                Env.insert_line(-2 * i, 2 * DP[t][i] + i * i - i + 2 * Pref[i], i);
                for (int j = i; j < N && (j&i) == i; ++j) {
                    ll best = (j + 1) * (j + 2) - 2 * Pref[j+1] + Env[j+1];
                    Fragments[t][i].push_back(best / 2);
                }
                auto cur = ((i + 1) * (i + 2) - 2 * Pref[i + 1] + Env[i + 1]) / 2;
                DP[t][i + 1] = max(DP[t][i], cur);
            }
            reverse(T.begin(),T.end());
        }

        vector<ll> With(N, -1e12), Without(N);
        for (int i = 0; i < N; ++i) {
            Without[i] = DP[0][i] + DP[1][N-1-i];
//            With[i] = ST.get(i);
        }

        for (int t = 0; t < 2; ++t) {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < Fragments[t][i].size(); ++j) {
                    Fragments[t][i][j] += DP[1-t][N - i - j];
                }
                for (int j = int(Fragments[t][i].size())-1; j > 0; --j) {
                    Fragments[t][i][j-1] = max(Fragments[t][i][j-1], Fragments[t][i][j]);
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < Fragments[0][i].size(); ++j) {
                With[i] = max(With[i], Fragments[0][i][j]);
                With[i + j] = max(With[i + j], Fragments[0][i][j]);
            }
            for (int j = 0; j < Fragments[1][i].size(); ++j) {
                With[N-1-i] = max(With[N-1-i], Fragments[1][i][j]);
                With[N-1-i-j] = max(With[N-1-i-j], Fragments[1][i][j]);
            }
        }

        for (pii p: P) {
            p.x--;
            cout << max(Without[p.x], max(0LL, With[p.x] + T[p.x] - p.y)) << '\n';
        }
    }
};



int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	FContestWithDrinksHard solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}



Measured memory_bytes: 91104