class SparseTable {
 public:
    vector<int> e;
    vector<int> a;
    vector<int> logTable;
    vector<vector<int>> rmq;
    SparseTable(vector<int>& a1, vector<int>& e1) {
        a = a1;
        e = e1;
        int n = a.size();
        logTable.resize(n + 1);

        for (int i = 2; i <= n; ++i) {
            logTable[i] = logTable[i >> 1] + 1;
        }
        rmq.resize(logTable[n] + 1);
        for (auto& i : rmq) {
            i.resize(n);
        }
        for (int i = 0; i < n; ++i) {
            rmq[0][i] = i;
        }
        for (int k = 1; (1 << k) < n; ++k) {
            for (int i = 0; i + (1 << k) < n + 1; ++i) {
                int x = rmq[k - 1][i];
                int y = rmq[k - 1][i + (1 << k - 1)];
                rmq[k][i] = a[x] <= a[y] ? x : y;
            }
        }
    }
    int get(int i, int j) {
        if (i > j) {
            swap(i, j);
        }
        int k = logTable[j - i];
        int x = rmq[k][i];
        int y = rmq[k][j - (1 << k) + 1];
        return a[x] < a[y] ? e[x] : e[y];
    }
};