#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX = 2e5;

struct vertex
{
    int res;
    int left;
    int right;
};

class Segment_Tree
{
    struct vertex* tree;
    int tree_size;
    int count_numbers;
    std::vector<int> numbers;

public:
    void build_tree(int v, int tl, int tr);
    int to_deg_of_two(std::vector<int>& numbers, int count_numbers);
    void Initialize(int count_numbers);
    void set(int k, int x);
    int get_min(int node, int a, int b);
    int find_spot(char* start_number);
    int free_up(char* number);
    void print_tree();
};

void Segment_Tree::build_tree(int v, int tl, int tr)
{

    //cout << "numbers:" << endl;
    //for (int j  = 0; j < this->numbers.size(); ++j)
    //    cout << numbers[j] << " ";
    //cout << endl;

    if (tr - tl == 1)
    {
        //cout << "* tl, tr  = " << tl << " " << tr;
        tree[v].res = this->numbers[tl];
        tree[v].left = tl;
        tree[v].right = tr;
        //cout << " v = " << v <<  " tree[v] = " << tree[v].res << endl;
        //print_tree();
        //cout << "-------------" << endl;
    }
    else
    {
        //cout << " tl, tr  = " << tl << " " << tr << endl;
        int tm = (tl + tr) / 2;
        build_tree(v * 2 + 1, tl, tm);
        build_tree(v * 2 + 2, tm, tr);
        tree[v].left = tl;
        tree[v].right = tr;

        if (tree[v * 2 + 1].res < tree[v * 2 + 2].res)
            tree[v].res = tree[v * 2 + 1].res;
        else
            tree[v].res = tree[v * 2 + 2].res;

        //print_tree();
        //cout << "-------------" << endl;
        //cout << "v = " << v <<  " tree[v] = " << tree[v].res << endl;
    }
}

int Segment_Tree::to_deg_of_two(std::vector<int>& numbers, int count_numbers)
{

    int p = 1;
    while (count_numbers > p)
        p *= 2;

    for (int i = 0; i < p - count_numbers; ++i)
        this->numbers.push_back(MAX);

    return p;
}

void Segment_Tree::Initialize(int count_numbers)
{



    this->count_numbers = count_numbers;
    this->numbers.clear();
    this->numbers.resize(count_numbers);

    for (int i = 1; i <= count_numbers; ++i)
        this->numbers[i-1] = i;

    this->count_numbers = to_deg_of_two(numbers, count_numbers);
    this->tree_size = 2*this->count_numbers-1;
    this->tree = new vertex[tree_size];
    build_tree(0, 0, this->count_numbers);
}


void Segment_Tree::set(int k, int x)
{
    int v = this->count_numbers -1 + k;
    tree[v].res = x;
    while (v > 0)
    {
        v = (v - 1) / 2;

        int l_min = tree[2 * v + 1].res;
        int r_min = tree[2 * v + 2].res;
        (l_min < r_min) ? tree[v].res = l_min : tree[v].res = r_min;
    }
}

int Segment_Tree::get_min(int node, int a, int b)
{
    int l = tree[node].left;
    int r = tree[node].right;
    if (r <= a || l >= b)
        return MAX;

    if (r < b & l >= a)
        return tree[node].res;

    int m1 = get_min(node * 2 + 1, a, b);
    int m2 = get_min(node * 2 + 2, a, b);
    return (m1 < m2) ? m1 : m2;
}

int Segment_Tree::find_spot(char* start_number)
{

    int start = stoi(start_number);
    int min_num = get_min(0, start, this->count_numbers - 1);

    if (min_num == MAX)
    {
        min_num = get_min(0, 0, start - 1);

        if (min_num == MAX)
            return -1;
        else
        {
            set(min_num - 1, MAX);
            return min_num;
        }
    }

    else
    {
        set(min_num - 1, MAX);
        return min_num;
    }
}

int Segment_Tree::free_up(char* number)
{
    int num = stoi(number);

    if (tree[num - 1].res == MAX)
    {
        set(num - 1, num);
        return 0;
    }
    else
        return -2;
}

void Segment_Tree::print_tree()
{
    int k = 2;
    cout << "\ni= " << 0 << " (" << tree[0].left << ";" << tree[0].right << "): " << tree[0].res << endl;
    for (int i=1; i < this->tree_size; ++i)
    {
        if (i == 2*k-1)
        {
            k *= 2;
            cout << endl;
        }
        cout << "i= " << i << " (" << tree[i].left << ";" << tree[i].right << "): " << tree[i].res << "; ";
    }
    cout << endl;
}

int main()
{

    //int n, m;
    //cin >> n >> m;

    Segment_Tree tree;
    tree.Initialize(7);
    //tree.print_tree();


    cout << tree.get_min(0, 0, 6) << endl;
    tree.set(0, 5);
    cout << tree.get_min(0, 0, 6) << endl;
    tree.set(6, 1);
    tree.print_tree();
    cout << tree.get_min(0, 0, 8) << endl;


/*
    string s;
    for (int i = 0; i < m; ++i)
    {
        cin >> s;
        char c = s[3];
        if (s[0] == '+')
            tree.find_spot(&c);
        else
            tree.free_up(&c);
    }
*/
    return 0;
}