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

struct Node{
    Node * l, * r;
    int value;
};

vector<Node *> versions;


Node * newNode(){
    Node * kek = new Node();
    return kek;
}

Node * Build(int v, int tl, int tr, vector<int> & a){
    if(tl == tr){
        auto leave  = newNode();
        leave->l = NULL;
        leave->r = NULL;
        leave->value = a[tl];
        return leave;
    } else {
        int tm = (tl + tr)/2;
        auto L = Build(v, tl, tm, a);
        auto R = Build(v, tm+1, tr, a);
        auto V = newNode();
        V->l = L;
        V->r = R;
        V->value = max(L->value,R->value);
        return V;
    }
}


int get(Node * v, int tl, int tr, int l, int r){
    if(l > r) return 0;
    if(l == tl  && r == tr){
        return v->value;
    } else {
        int tm = (tl + tr) / 2;
        int lAns = get(v->l, tl, tm, l, min(r, tm));
        int rAns = get(v->r, tm+1,tr, max(tm+1,l),r);
        return max(rAns,lAns);
    }
}

Node * upd(Node * v, int tl, int tr, int i, int value){
    if(tl == tr){
        auto curV = newNode();
        curV->l = NULL;
        curV->r = NULL;
        curV->value = value;
        return curV;
    } else {
        int tm = (tl + tr) / 2;
        if(i <= tm){
            auto lUpd = upd(v->l, tl, tm, i, value);
            auto curV = newNode();
            curV->r = v -> r;
            curV->l = lUpd;
            curV->value = max(lUpd->value, v->r->value);
            return curV;
        } else {
            auto rUpd = upd(v->r, tm+1,tr, i, value);
            auto curV = newNode();
            curV->r = rUpd;
            curV->l = v->l;
            curV->value = max(v->l->value, rUpd->value);
            return curV;
        }
    }
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  return 0;
}