#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <ctime>
using std::cin;
using std::cout;
using std::vector;
std::mt19937 gen;

vector<int> precount_log;
vector<int> precount_pow;

class FastRMQ {
 public:
    explicit FastRMQ(vector<int> &data);
    int request(int l, int r);
 private:
    vector<int> start_data;
    void precount_logparts();
    int halflog;
    vector<int> parttype;
    vector<vector<int>> body;
    vector<vector<vector<int>>> log_parts_answer;
};
FastRMQ::FastRMQ(vector<int> &d) : start_data(d) {
    halflog = int(log2(start_data.size()) / 2);
    int big = start_data[start_data.size() - 1] + 1;
    while (start_data.size() % halflog != 0) {
        start_data.push_back(big);
    }
    //предпосчёт логарифмов
    for (int i = 0; i < start_data.size() + 1; ++i) {
        precount_log.push_back(int(std::log2(i)));
    }
    for (int pow:precount_log) {
        precount_pow.push_back(int(std::pow(2, pow)));
    }
    //предподсчёт кусков размера halflog
    precount_logparts();

    for (int i = 0; i < start_data.size(); i += halflog) {
        int type = 0;
        for (int j = halflog - 2; j >= 0; --j) {
            type = type * 2 + (1 + start_data[i + j + 1] - start_data[i + j]) / 2;
        }
        parttype.push_back(type);
    }
    //строим стандартный SparseTable
    body.emplace_back();
    for (int i = 0; i < start_data.size() / halflog; ++i) {
        body[0].push_back(log_parts_answer[parttype[i]][0][halflog - 1] + start_data[i * halflog]);
    }
    for (int partsize = 2; partsize < (start_data.size() / halflog); partsize *= 2) {
        body.emplace_back();
        int size = body.size() - 1;
        for (int i = 0; i < (start_data.size() / halflog) - partsize + 1; ++i) {
            body[size].push_back(std::min(body[size - 1][i], body[size - 1][i + partsize / 2]));
        }
    }
}
void FastRMQ::precount_logparts() {
    for (int number = 0; number < pow(2, halflog - 1); ++number) {
        log_parts_answer.emplace_back();
        vector<int> curr_vector(1, 0);
        for (int counter = 0, localnumber = number; counter < halflog - 1; ++counter) {
            curr_vector.push_back(curr_vector[curr_vector.size() - 1] - 1 + 2 * (localnumber % 2));
            localnumber /= 2;
        }
        for (int l = 0; l < halflog; ++l) {
            log_parts_answer[number].emplace_back();
            int localmin = curr_vector[l];
            for (int r = l; r < halflog; ++r) {
                localmin = std::min(localmin, curr_vector[r]);
                log_parts_answer[number][l].push_back(localmin);
            }
        }
    }
}
int FastRMQ::request(int l, int r) {
    if (l / halflog == r / halflog) {
        return start_data[l - l % halflog] + log_parts_answer[parttype[l / halflog]][l % halflog][r - l];
    } else {
        int leftborlder = l / halflog + 1;
        int rightborder = r / halflog - 1;
        int middleanswer = 2e9;
        int curlog = precount_log[rightborder - leftborlder + 1];
        int max_size = precount_pow[rightborder - leftborlder + 1];
        if (leftborlder <= rightborder) {
            middleanswer = std::min(body[curlog][leftborlder], body[curlog][rightborder - max_size + 1]);
        }
        int leftanswer = start_data[l - l % halflog]
            + log_parts_answer[parttype[leftborlder - 1]][l % halflog][halflog - 1 - l % halflog];
        int rightanswer = start_data[r - r % halflog] + log_parts_answer[parttype[rightborder + 1]][0][r % halflog];
        return std::min(std::min(leftanswer, rightanswer), middleanswer);
    }
}

int main() {
    gen.seed(time(0));

    int n, m;
    m = 10;
    cin >> n;;

    vector<int> data;
    int d = 0;
    for (int i = 0; i < n; ++i) {
        d += 1;
        d -= 2 * gen() % 2;
        data.push_back(d);
    }
    FastRMQ test(data);
    for (int i = 0; i < m; ++i) {
        int l, r;
        r = 1 + gen() % (n - 1);
        l = gen() % r;
        int stupidans = 2e9;
        for (int j = l; j <= r; ++j) {
            stupidans = std::min(stupidans, data[j]);
        }
        int x = test.request(l, r);
        if (x == stupidans) {
            cout << "\nTEST PASSED:\nl=" << l << "\nr=" << r << "\nanswer=" << x;
        } else {
            cout << "\nTEST FAILED:\nl=" << l << "\nr=" << r << "\nn=" << n;
            cout << "UDSCBUDnjavdnjcnsanvdnjdv\nirwvnjcljvkhqwbk\newkjhjewbkvuh\nkgwuehbefkvguw\neuwfhvbuwhe";
        }

    }
    return 0;
}