//https://atcoder.jp/contests/awc0150/submissions/79608947
// generated by ChatGPT outside of contest time.
#include <algorithm>
#include <cassert>
#include <vector>

template <class S, S (*op)(S, S), S (*e)()>
struct disjoint_sparse_table {
  public:
    disjoint_sparse_table() : disjoint_sparse_table(0) {}

    explicit disjoint_sparse_table(int n)
        : disjoint_sparse_table(std::vector<S>(n, e())) {}

    explicit disjoint_sparse_table(const std::vector<S>& v)
        : _n((int)v.size()), data_(v) {
        log_ = 0;
        while ((1LL << log_) < _n) ++log_;

        table_.assign(log_, std::vector<S>(_n, e()));

        for (int k = 0; k < log_; ++k) {
            const long long half = 1LL << k;
            const long long block = half << 1;

            for (long long l = 0; l < _n; l += block) {
                const int m =
                    (int)std::min<long long>(l + half, _n);
                const int r =
                    (int)std::min<long long>(l + block, _n);

                // 左半分: suffix
                if ((int)l < m) {
                    table_[k][m - 1] = data_[m - 1];
                    for (int i = m - 2; i >= (int)l; --i) {
                        table_[k][i] =
                            op(data_[i], table_[k][i + 1]);
                    }
                }

                // 右半分: prefix
                if (m < r) {
                    table_[k][m] = data_[m];
                    for (int i = m + 1; i < r; ++i) {
                        table_[k][i] =
                            op(table_[k][i - 1], data_[i]);
                    }
                }
            }
        }
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return data_[p];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);

        if (l == r) return e();
        if (l + 1 == r) return data_[l];

        const unsigned x =
            static_cast<unsigned>(l ^ (r - 1));
        const int k = 31 - __builtin_clz(x);

        return op(table_[k][l], table_[k][r - 1]);
    }

    S all_prod() const {
        return prod(0, _n);
    }

    template <bool (*f)(S)>
    int max_right(int l) const {
        return max_right(l, f);
    }

    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));

        if (l == _n) return _n;
        if (f(prod(l, _n))) return _n;

        int ok = l;
        int ng = _n;

        while (ng - ok > 1) {
            const int m = ok + (ng - ok) / 2;

            if (f(prod(l, m))) {
                ok = m;
            } else {
                ng = m;
            }
        }

        return ok;
    }

    template <bool (*f)(S)>
    int min_left(int r) const {
        return min_left(r, f);
    }

    template <class F>
    int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));

        if (r == 0) return 0;
        if (f(prod(0, r))) return 0;

        int ng = 0;
        int ok = r;

        while (ok - ng > 1) {
            const int m = ng + (ok - ng) / 2;

            if (f(prod(m, r))) {
                ok = m;
            } else {
                ng = m;
            }
        }

        return ok;
    }

  private:
    int _n;
    int log_;
    std::vector<S> data_;
    std::vector<std::vector<S>> table_;
};