template<typename T>
class STtable {
    vector<size_t> Log2;
    vector<vector<T>> values;
    size_t maxn;
    bool build = false;
    function<T(const T&, const T&)> fun;
    function<T(const T&, const T&)> default_max = [](const T&a, const T&b)->T { return a >= b ? a : b;};
    function<T(const T&, const T&)> default_min = [](const T&a, const T&b)->T { return b >= a ? a : b;};
public:
    STtable(
        size_t maxn,
        function<T(const T&, const T&)> _fun = function<T(const T&, const T&)>(),
        bool is_max = true
    ) : Log2(maxn + 1), maxn(maxn) {
        Log2[1] = 0;
        Log2[2] = 1;
        for (size_t i = 3; i <= maxn; i++) {
            Log2[i] = Log2[i / 2] + 1;
        }
        values.resize(Log2[maxn] + 1, vector<T>(maxn + 1));
        if (_fun) {
            fun = _fun;
        } else {
            fun = (is_max ? default_max : default_min);
        }
    }
    inline size_t logn() {
        return Log2.back();
    }
    inline size_t size() {
        return maxn;
    }
    T& operator()(const size_t& k) {
        return values[0][k];
    }
    T operator()(const size_t& i, const size_t& j) {
        if (!build) {
            for (size_t jj = 1; jj <= logn(); ++jj) {
                for (size_t ii = 1; ii + (1 << jj) - 1 <= size(); ++ii) {
                    values[jj][ii] = fun(values[jj - 1][ii], values[jj - 1][ii + (1 << (jj - 1))]);
                }
            }
            build = true;
        }
        size_t s = Log2[j - i + 1];
        return fun(values[s][i], values[s][j - (1 << s) + 1]);
    }
};