GSS1

gss1.cpp

/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)


/** I/O Accelerator **/

/* ... :" We are I/O Accelerator ... Use us at your own risk ;) ... " .. */

template<class T> inline void RD(T &);
template<class T> inline void OT(const T &);
inline int RD(){ int x; RD(x); return x;}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
// <<= ` 0. Daily Use .,
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}


// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';

}

template<class T> inline void OT(const T &x){
    printf("%d\n", x);
}

/* .................................................................................................................................. */

const int N = 50001;

struct Seg{
    int ss, ls, rs, ms;
} T[4*N];
int A[N], n, a, b;

#define root 1, 1, n
#define lx (x << 1)
#define rx (lx + 1)
#define lc lx, l, m
#define rc rx, m+1, r

void Update(Seg &x, Seg l, Seg r){
    x.ss = l.ss + r.ss;
    x.ls = max(l.ls, l.ss + r.ls);
    x.rs = max(r.rs, r.ss + l.rs);
    x.ms = max(l.ms, r.ms, l.rs + r.ls);
}

void Build(int x, int l, int r){
    if (l == r){
        T[x].ss = T[x].ls = T[x].rs = T[x].ms = A[l];
    }
    else{
        int m = (l + r) >> 1;
        Build(lc), Build(rc);
        Update(T[x], T[lx], T[rx]);
    }
}

void Modify(int x, int l, int r){
    if (l == r){
        T[x].ss = T[x].ls = T[x].rs = T[x].ms = b;
    }
    else {
        int m = (l + r) >> 1;
        if (a <= m) Modify(lc); if (m < a) Modify(rc);
        Update(T[x], T[lx], T[rx]);
    }
}

Seg Query(int x, int l, int r){
    if (a <= l && r <= b)
        return T[x];
    else {
        int m = (l + r) >> 1;
        if (b <= m) return Query(lc); if (m < a) return Query(rc);
        Seg res; Update(res, Query(lc), Query(rc)); return res;
    }
}

int main(){

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(false);

    RD(n); REP_1(i, n) RD(A[i]);
    Build(root);

    DO_C(RD()){
        RD(a, b), OT(Query(root).ms);
    }
}