#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

struct SegmentTree {
    vector<int> t;
    SegmentTree(int n) : t(n * 4) {}

    void Build(int v, int tl, int tr, vector<int>& arr) {
        if (tl + 1 == tr) {
            t[v] = arr[tl];
        } else {
            int tm = (tl + tr) / 2;
            Build(v * 2 + 1, tl, tm, arr);
            Build(v * 2 + 2, tm, tr, arr);
            t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
        }
    }
    void Update(int v, int tl, int tr, int index, int value) {
        if (tl + 1 == tr) {
            t[v] = value;
        } else {
            int tm = (tl + tr) / 2;
            if (index < tm) {
                Update(v * 2 + 1, tl, tm, index, value);
            } else {
                Update(v * 2 + 2, tm, tr, index, value);
            }
            t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
        }
    }
    int LowerBound(int v, int tl, int tr, int x, int y) {
        if (tr - 1 < x || t[v] < y) return -1;
        if (tl + 1 == tr) {
            return tl;
        } else {
            int tm = (tl + tr) / 2;
            int ans = LowerBound(v * 2 + 1, tl, tm, x, y);
            if (ans == -1) {
                ans = LowerBound(v * 2 + 2, tm, tr, x, y);
            }
            return ans;
        }
    }

};

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

}