ABC 343

struct S {
    ll fir, fn;
    ll sec, sn;
};

S op(S a, S b) {
    map<ll, ll> mp;
    mp[a.fir] += a.fn;
    mp[a.sec] += a.sn;
    mp[b.fir] += b.fn;
    mp[b.sec] += b.sn;

    auto it = mp.rbegin();
    ll fir = it->first, fn = it->second;
    it++;
    ll sec = it->first, sn = it->second;
    return {fir, fn, sec, sn};
}

S e() {
    return S({0, 0, 0, 0});
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    vll A(N);
    rep(i, N) cin >> A[i];

    segtree<S, op, e> seg(N);
    rep(i, N) {
        seg.set(i, {A[i], 1, 0, 0});
    }

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            ll p, x;
            cin >> p >> x;
            p--;
            seg.set(p, {x, 1, 0, 0});
        } else {
            ll l, r;
            cin >> l >> r;
            l--;
            S v = seg.prod(l, r);
            cout << v.sn << endl;
        }
    }
}