可以发现，如果一个数被选择，相邻两个数一定不会被选。

然后找点性质，对于一个极大单调区间而言，它的极大值肯定是要被选的。

这个十分的好证明，从略。

然后这两个性质叠在一起，可以发现跟奇偶性有关。

然后进一步找到极小值，考虑什么时候会贡献。

当且仅当到达两边极大值的距离均为偶数时才会贡献。

修改的话，最多将两个区间合并成一个区间，也就涉及五个极值。

直接暴力维护即可。

#define ite set<int>::iterator
const int N = 1e5 + 5;

int n, a[N]; set<int> s;

struct Bit {
    ll c[N];
    il void upd(int x, int d) {
        for (; x <= n + 1; x += x & -x) c[x] += d;
    } il void qry(int l, int r, ll &v) { //( ]
        for (; r; r -= r & -r) v += c[r];
        for (; l; l -= l & -l) v -= c[l];
    }
} b[2]; ll ans;

#define od(o) ((*l ^ *(o(j = l))) & 1)

void change(ite l, ite r, int op) {
    ite i, j; ll sum = (a[*l] < a[*l + 1] && *l && !od(++) && !od(--)) ? a[*l] : 0;
    for (i = l++; i != r; i = l++) {
        if (a[*l] > a[*i]) b[*l & 1].qry(*i, *l, sum);
        else b[*i & 1].qry(*i, *l - od(++), sum);
    } ans += sum * op;
}

void upd(int x) {
    if ((a[x] > a[x - 1]) != (a[x + 1] > a[x])) s.insert(x);
    else s.erase(x);
} 

void modify(int x) {
    int y; qr(y);
    ite i = s.lower_bound(x), l = i, r = i; --l;
    if (l != s.begin()) --l; ++r; if (r == s.end() || (*i == x && ++r == s.end())) --r;
    change(l, r, -1); b[x & 1].upd(x, y - a[x]); a[x] = y;
    upd(x); if (x > 1) upd(x - 1); if (x < n) upd(x + 1);
    change(l, r, 1);    
}

void solve() {
    qr(n); s.insert(0); s.insert(n + 1);
    rep (i, 1, n) modify(i);
    int m; qr(m);
    rep (i, 1, m) {int x; qr(x); modify(x); pr2(ans);}
}