void add(int s, int t, int x) { // 修改(s, t) O(logn)
    int A;
    for (s=l+M-1, t=r+M+1; s^t^1; s>>=1, t>>=1) {
        if (~s&1) q[s^1] += x;
        if (t&1) q[t^1] += x;
        A = max(q[s], q[s^1]), q[s] -= A, q[s^1] -= A, q[s>>1] += A;
        A = max(q[t], q[t^1]), q[t] -= A, q[t^1] -= A, q[t>>1] += A;
    }
    while (s>1) {
        int A = max(q[s], q[s^1]); q[s] -= A, q[s^1] -= A, q[s>>=1] += A;
    }
}

int query(int s, int t) { // 查询(s, t)上最大值 O(logn)
    int lans = 0, rans = 0; // 分别是从左到右遇到的最大值和从右到左遇到的最大值
    for (s=s+M-1, t=t+M+1; s^t^1; s>>=1, t>>=1) {
        lans += q[s], rans += q[t];
        if (~s&1) lans = max(lans, q[s^1]); // 和右节点比较
        if (t&1) rans = max(rans, q[t^1]); // 和左节点比较
    }
    int ans = max(lans, rans);
    while (s > 1) ans += q[s>>=1];
    return ans;
}