GSS1

        #include<bits/stdc++.h>
        using namespace std;
        #define int long long
        #define MAXI (1e6+5)
        #define N 50010

        int n, a[N];

        struct node{
            int sum, prefix, suffix, ans;
        };

        node seg[5*N];

        node data(int x)
        {
            node pawan;
            pawan.sum = pawan.prefix = pawan.suffix = pawan.ans = x;
            return pawan;
        }

        node merge(node x, node y)
        {
            node pawan;

            if(x.sum==-MAXI)
            {
                pawan.sum = y.sum;
                pawan.prefix = y.prefix;
                pawan.suffix = max(y.suffix , y.sum);
                pawan.ans = max(y.ans,y.prefix);
            }
            else
            {
                pawan.sum = x.sum + y.sum;
                pawan.prefix = max(x.prefix , x.sum + y.prefix);
                pawan.suffix = max(y.suffix , y.sum + x.suffix);
                pawan.ans = max(max(x.ans, y.ans) , x.suffix + y.prefix);
            }

            return pawan;
        }

        void build(int id, int l, int r)
        {
            if(l>r)
                return;

            if(l==r)
            {
                seg[id] = data(a[l]);
                return ;
            }
            int mid = (l+r)/2;
            build(2 * id,l,mid);
            build(2 * id + 1,mid+1,r);

            seg[id] = merge(seg[2*id], seg[2*id+1]);

        }

        void update(int x, int y, int id, int l, int r)
        {

            if(l==r)
            {
                seg[id] = data(y);
                return ;
            }

            int mid = (l+r)/2;
            if(x<=mid)
                update(x,y,2 * id,l,mid);
            else
                update(x,y,2 * id + 1,mid+1,r);

            seg[id] = merge(seg[2*id], seg[2*id+1]);
        }

        node segment(int x, int y, int id, int l, int r)
        {
            if(l>r or l > y || x > r)
                return data(-MAXI);

            if(x <= l && r <= y)
                return seg[id];

            int mid = (l+r)/2;
            node a = segment(x,y,2 * id,l,mid);
            node b = segment(x,y,2 * id + 1,mid+1,r);

            return merge(a,b);
        }


        // Driver code to test above functions
        int32_t main()
        {

            #ifndef ONLINE_JUDGE
            // for getting input from inpu.txt
            freopen("input.txt", "r", stdin);
            // for writing output to output.txt
            //freopen("output.txt", "w", stdout);
            #endif

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

            cin >> n;
            for(int i=0;i<n;i++)
                cin >> a[i];// a[i];

            build(1,0,n-1);

            int q;
            cin >> q;
            while(q--)
            {
               int type, x, y;
                cin >> x >> y;
                x--;y--;
                // if(type==0)
                // {
                //     y++;
                //     update(x,y,1,0,n-1);
                // }
                // else
                    cout << segment(x,y,1,0,n-1).ans << endl;
            }

            return 0;
        }