#include <bits/stdc++.h>
using namespace std;

struct SegmentTree{
    typedef pair<int, int> pii;
    static const int sz = 1 << 17; // sz > MAX_SIZE
    static const int inf = 1e9+7;
    static pii merge(pii a, pii b){
        if(a.first > b.first) return a;
        if(a.first < b.first) return b;
        if(a.second < b.second) return a;
        return b;
    }
    pii tree[sz << 1];
    void init(int n){
        for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
        for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
    }
    void update(int x, int v){
        x += sz; tree[x].first = v;
        while(x /= 2) tree[x] = merge(tree[x*2], tree[x*2+1]);
    }
    int query(int l, int r){
        l += sz; r += sz; pii ret(-inf, inf);
        while(l <= r){
            if(l % 2 == 1) ret = merge(ret, tree[l++]);
            if(r % 2 == 0) ret = merge(ret, tree[r--]);
            l /= 2; r /= 2;
        }
        return ret.second;
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int initialArray[4] = {5, 4, 3, 9};
    SegmentTree ST; ST.init(4);
    for(int i=0; i<4; i++) ST.update(i, initialArray[i]);
    
    ST.update(2, 4); // first query (2, 4), [5, 4, 4, 9]
    cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
    ST.update(0, 100); // first query (0, 100), [100, 4, 4, 9]
    ST.update(3, 100); // first query (3, 100), [100, 4, 4, 100]
    cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
}