import java.util.Arrays;
import static java.lang.Math.*;

public class AddSegmentTree {
    int n;
    int[] treeSum;
    int[] treeMax;
    int[] add;
    int[] len;
    boolean[] pushed;

    public AddSegmentTree(int[] arr) {
        n = arr.length;
        treeSum = new int[4*n + 1];
        treeMax = new int[4*n + 1];
        add = new int[4*n + 1];
        len = new int[4*n + 1];
        pushed = new boolean[4*n + 1];
        Arrays.fill(pushed, true);
        build(1, 0, n-1, arr);
    }

    private void build(int v, int L, int R, int[] arr) {
        len[v] = R - L + 1;
        if (L == R) {
            treeSum[v] = arr[L];
            treeMax[v] = arr[L];
            return;
        }
        int m = (L + R) >> 1;
        build(2*v, L, m, arr);
        build(2*v+1, m+1, R, arr);
        update(v);
    }

    private void update(int v) {
        treeSum[v] = treeSum[2*v] + add[2*v]*len[2*v] +
                     treeSum[2*v+1] + add[2*v+1]*len[2*v+1];
        treeMax[v] = max(treeMax[2*v] + add[2*v],
                         treeMax[2*v+1] + add[2*v+1]);
        add[v] = 0;
    }

    private void push(int v) {
        if (pushed[v]) return;
        pushed[v] = true;
        int delta = add[v];
        add[v] = 0;
        treeSum[v] += delta*len[v];
        treeMax[v] += delta;
        if (len[v] == 1) return;
        add[2*v] += delta;
        add[2*v+1] += delta;
        pushed[2*v] = pushed[2*v+1] = false;
    }

    public void inc(int v, int L, int R, int needL, int needR, int delta) {
        if (L == needL && R == needR) {
            add[v] += delta;
            pushed[v] = false;
            return;
        }
        push(v);
        int m = (L + R) >> 1;
        if (needR <= m) {
            inc(2*v, L, m, needL, needR, delta);
        } else if (m+1 <= needL) {
            inc(2*v+1, m+1, R, needL, needR, delta);
        } else {
            inc(2*v, L, m, needL, m, delta);
            inc(2*v+1, m+1, R, m+1, needR, delta);
        }
        update(v);
    }

    public int getSum(int v, int L, int R, int needL, int needR) {
        if (L == needL && R == needR) {
            return treeSum[v] + add[v]*len[v];
        }
        push(v);
        int m = (L + R) >> 1;
        if (needR <= m) {
            return getSum(2*v, L, m, needL, needR);
        } else if (m+1 <= needL) {
            return getSum(2*v+1, m+1, R, needL, needR);
        } else {
            int a = getSum(2*v, L, m, needL, m);
            int b = getSum(2*v+1, m+1, R, m+1, needR);
            return a + b;
        }
    }

    public int getMax(int v, int L, int R, int needL, int needR) {
        if (L == needL && R == needR) {
            return treeMax[v] + add[v];
        }
        push(v);
        int m = (L + R) >> 1;
        if (needR <= m) {
            return getMax(2*v, L, m, needL, needR);
        } else if (m+1 <= needL) {
            return getMax(2*v+1, m+1, R, needL, needR);
        } else {
            int a = getMax(2*v, L, m, needL, m);
            int b = getMax(2*v+1, m+1, R, m+1, needR);
            return max(a, b);
        }
    }
}