class segtree {
#define lson (root << 1)
#define rson (root << 1 | 1)

    int n;
    vector<LL> max;
    vector<LL> lazy;

    void build(int root, int l, int r, const vector<int> &v, const vector<LL> &val) {
        if (l == r) {
          lazy[root] = 0;
          max[root] = val[v[l - 1]];
          return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, v, val);
        build(rson, mid + 1, r, v, val);
        max[root] = std::max(max[lson], max[rson]);
        lazy[root] = 0;
    }

    inline void pushdown(int root){
        if (lazy[root]){
            lazy[lson] += lazy[root];
            max[lson] += lazy[root];
            lazy[rson] += lazy[root];
            max[rson] += lazy[root];
            lazy[root] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, LL val){
        if (L <= l && r <= R){
            lazy[root] += val;
            max[root] += val;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update(lson, l, mid, L, R, val);
        if (R > mid)
            update(rson, mid + 1, r, L, R, val);
        max[root] = std::max(max[lson], max[rson]);
    }

    LL query(int root, int l, int r, int pos){
        if (l == r)
            return max[root];
        pushdown(root);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return query(lson, l, mid, pos);
        else 
            return query(rson, mid + 1, r, pos);
    }

    public:

    void build(const vector<int> &v, const vector<LL> &val){
        n = v.size();
        lazy.resize(4 * (n + 1), 0);
        max.resize(4 * (n + 1), 0);
        build(1, 1, n, v, val);
    }

    void update(int L, int R, LL val){
        assert(1 <= L && R <= n && L <= R);
        update(1, 1, n, L, R, val);
    }

    LL query(int pos){
        return query(1, 1, n, pos);
    }

};