void build(int ind, int l, int r) {
    if (l == r) {
        t[ind] = arr[l];
        return;
    }
    int d = (l + r) / 2;
    build(ind * 2, l, d);
    build(ind * 2 + 1, d + 1, r);
    t[ind] = max(t[ind * 2], t[ind * 2 + 1]);
}

void push(int ind) {
    if (p[ind] != 0) {
        t[ind * 2] += p[ind];
        t[ind * 2 + 1] += p[ind];
        p[ind * 2] += p[ind];
        p[ind * 2 + 1] += p[ind];
    }
    p[ind] = 0;
}

void update(int ind, int l, int r, int i, int j, ll val) {
    if (l == i && r == j) {
        t[ind] += val;
        p[ind] += val;
        return;
    }
    push(ind);
    int d = (l + r) / 2;
    if (j <= d) {
        update(ind * 2, l, d, i, j, val);
    } else if (d + 1 <= i) {
        update(ind * 2 + 1, d + 1, r, i, j, val);
    } else {
        update(ind * 2, l, d, i, d, val);
        update(ind * 2 + 1, d + 1, r, d + 1, j, val);
    }
    t[ind] = max(t[ind * 2], t[ind * 2 + 1]);
}

ll get_max(int ind, int l, int r, int i, int j) {
    if (l == i && r == j) {
        return t[ind];
    }
    push(ind);
    int d = (l + r) / 2;
    if (j <= d) {
        return get_max(ind * 2, l, d, i, j);
    } else if (d + 1 <= i) {
        return get_max(ind * 2 + 1, d + 1, r, i, j);
    } else {
        return max(get_max(ind * 2, l, d, i, d),
                   get_max(ind * 2 + 1, d + 1, r, d + 1, j));
    }
}