// generated by ChatGPT outside of contest time.
namespace implicit_treap_detail {

template <class S>
S disabled_op(S, S) {
    std::abort();
}

template <class S>
S disabled_e() {
    std::abort();
}

template <class S, class F>
S disabled_mapping(F, S) {
    std::abort();
}

template <class F>
F disabled_composition(F, F) {
    std::abort();
}

template <class F>
F disabled_id() {
    std::abort();
}


// aggregate を使わないときは空クラス
template <class S, bool Enabled>
struct aggregate_storage {
    explicit aggregate_storage(const S&) {}
};

template <class S>
struct aggregate_storage<S, true> {
    S fwd, bwd;

    explicit aggregate_storage(const S& x)
        : fwd(x), bwd(x) {}
};


// lazy を使わないときは空クラス
template <class F, bool Enabled, F (*Id)()>
struct lazy_storage {
    lazy_storage() = default;
};

template <class F, F (*Id)()>
struct lazy_storage<F, true, Id> {
    F tag;
    bool pending = false;

    lazy_storage() : tag(Id()) {}
};

}  // namespace implicit_treap_detail


template <
    class S,

    S (*op)(S, S)
        = implicit_treap_detail::disabled_op<S>,

    S (*e)()
        = implicit_treap_detail::disabled_e<S>,

    class F = S,

    S (*mapping)(F, S)
        = implicit_treap_detail::disabled_mapping<S, F>,

    F (*composition)(F, F)
        = implicit_treap_detail::disabled_composition<F>,

    F (*id)()
        = implicit_treap_detail::disabled_id<F>
>
class implicit_treap {
    static constexpr int nil = -1;

    static constexpr bool op_given =
        op != implicit_treap_detail::disabled_op<S>;

    static constexpr bool e_given =
        e != implicit_treap_detail::disabled_e<S>;

    static constexpr bool mapping_given =
        mapping != implicit_treap_detail::disabled_mapping<S, F>;

    static constexpr bool composition_given =
        composition != implicit_treap_detail::disabled_composition<F>;

    static constexpr bool id_given =
        id != implicit_treap_detail::disabled_id<F>;

public:

    static constexpr bool has_monoid =
        op_given && e_given;

    static constexpr bool has_lazy =
        mapping_given && composition_given && id_given;

private:

    static_assert(
        op_given == e_given,
        "implicit_treap: op and e must be specified together"
    );

    static_assert(
        mapping_given == composition_given &&
        composition_given == id_given,
        "implicit_treap: mapping, composition and id "
        "must be specified together"
    );

    static_assert(
        !has_lazy || has_monoid,
        "implicit_treap: lazy action requires op/e"
    );


    using Agg =
        implicit_treap_detail::aggregate_storage<
            S, has_monoid
        >;

    using Lazy =
        implicit_treap_detail::lazy_storage<
            F, has_lazy, id
        >;


    struct Node {
        int l = nil;
        int r = nil;

        int sz = 1;

        uint64_t pri = 0;

        bool rev = false;

        S val;

        [[no_unique_address]]
        Agg agg;

        [[no_unique_address]]
        Lazy lazy;

        Node(S x, uint64_t p)
            : pri(p),
              val(std::move(x)),
              agg(val),
              lazy() {}
    };


public:

    class sequence {
        friend class implicit_treap;

        implicit_treap* owner_ = nullptr;
        int root_ = nil;


        sequence(
            implicit_treap* owner,
            int root
        )
            : owner_(owner),
              root_(root) {}


        void check_owner() const {
            assert(owner_ != nullptr);
        }


        void release() {
            if (owner_ && root_ != nil) {
                owner_->release_tree(root_);
            }

            root_ = nil;
        }


    public:

        sequence() = default;


        sequence(const sequence&) = delete;
        sequence& operator=(const sequence&) = delete;


        sequence(sequence&& other) noexcept
            : owner_(other.owner_),
              root_(other.root_) {

            other.owner_ = nullptr;
            other.root_ = nil;
        }


        sequence& operator=(sequence&& other) noexcept {
            if (this == &other) {
                return *this;
            }

            release();

            owner_ = other.owner_;
            root_ = other.root_;

            other.owner_ = nullptr;
            other.root_ = nil;

            return *this;
        }


        ~sequence() {
            release();
        }


        // ------------------------------------------------------------
        // basic
        // ------------------------------------------------------------

        int size() const {
            check_owner();
            return owner_->node_size(root_);
        }


        bool empty() const {
            return size() == 0;
        }


        void clear() {
            check_owner();
            release();
        }


        // ------------------------------------------------------------
        // ACL: set / get
        // ------------------------------------------------------------

        void set(int p, S x) {
            check_owner();

            assert(
                0 <= p &&
                p < size()
            );

            owner_->set_impl(
                root_,
                p,
                std::move(x)
            );
        }


        S get(int p) {
            check_owner();

            assert(
                0 <= p &&
                p < size()
            );

            return owner_->get_impl(
                root_,
                p
            );
        }

		// ------------------------------------------------------------
	// to_vector
	//
	// to_vector()       : 列全体
	// to_vector(l, r)   : [l, r)
	//
	// 計算量:
	//   expected O(log n + (r - l))
	//   全体なら O(n)
	// ------------------------------------------------------------

	std::vector<S> to_vector() {
		check_owner();

		std::vector<S> res;
		res.reserve(size());

		owner_->to_vector_impl(
			root_,
			0,
			size(),
			res
		);

		return res;
	}


	std::vector<S> to_vector(int l, int r) {
		check_owner();

		assert(
			0 <= l &&
			l <= r &&
			r <= size()
		);

		std::vector<S> res;
		res.reserve(r - l);

		owner_->to_vector_impl(
			root_,
			l,
			r,
			res
		);

		return res;
	}

        // ------------------------------------------------------------
        // ACL: prod / all_prod
        // ------------------------------------------------------------

        S prod(int l, int r) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::prod requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= r &&
                    r <= size()
                );

                return owner_->prod_impl(
                    root_,
                    l,
                    r
                );
            }
        }


        S all_prod() const {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::all_prod requires op/e"
                );

                std::abort();

            } else {
                return root_ == nil
                    ? e()
                    : owner_->nodes_[root_].agg.fwd;
            }
        }


        // ------------------------------------------------------------
        // ACL: apply
        // ------------------------------------------------------------

        void apply(int p, F f) {
            check_owner();

            if constexpr (!has_lazy) {
                assert(
                    has_lazy &&
                    "implicit_treap::apply requires "
                    "mapping/composition/id"
                );

                std::abort();

            } else {
                assert(
                    0 <= p &&
                    p < size()
                );

                owner_->apply_point_impl(
                    root_,
                    p,
                    f
                );
            }
        }


        void apply(int l, int r, F f) {
            check_owner();

            if constexpr (!has_lazy) {
                assert(
                    has_lazy &&
                    "implicit_treap::apply requires "
                    "mapping/composition/id"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= r &&
                    r <= size()
                );

                owner_->apply_range_impl(
                    root_,
                    l,
                    r,
                    f
                );
            }
        }


        // ------------------------------------------------------------
        // ACL: max_right
        // ------------------------------------------------------------

        template <class G>
        int max_right(int l, G g) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::max_right requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= size()
                );

                S sm = e();

                assert(
                    std::invoke(g, sm)
                );

                if (l == size()) {
                    return size();
                }

                return owner_->max_right_impl(
                    root_,
                    l,
                    sm,
                    g
                );
            }
        }


        // ACL と同じ max_right<g>(l) 形式
        template <bool (*g)(S)>
        int max_right(int l) {
            return max_right(l, g);
        }


        // ------------------------------------------------------------
        // ACL: min_left
        // ------------------------------------------------------------

        template <class G>
        int min_left(int r, G g) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::min_left requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= r &&
                    r <= size()
                );

                S sm = e();

                assert(
                    std::invoke(g, sm)
                );

                if (r == 0) {
                    return 0;
                }

                return owner_->min_left_impl(
                    root_,
                    r,
                    sm,
                    g
                );
            }
        }


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


        // ------------------------------------------------------------
        // insert / erase
        // ------------------------------------------------------------

        void insert(int k, S x) {
            check_owner();

            assert(
                0 <= k &&
                k <= size()
            );

            int v =
                owner_->new_node(
                    std::move(x)
                );

            auto [a, b] =
                owner_->split_root(
                    root_,
                    k
                );

            root_ =
                owner_->merge_root(
                    owner_->merge_root(
                        a,
                        v
                    ),
                    b
                );
        }


        void erase(int k) {
            check_owner();

            assert(
                0 <= k &&
                k < size()
            );

            auto [a, bc] =
                owner_->split_root(
                    root_,
                    k
                );

            auto [b, c] =
                owner_->split_root(
                    bc,
                    1
                );

            assert(
                owner_->node_size(b) == 1
            );

            owner_->release_node(b);

            root_ =
                owner_->merge_root(
                    a,
                    c
                );
        }


        // ------------------------------------------------------------
        // reverse [l, r)
        // ------------------------------------------------------------

        void reverse(int l, int r) {
            check_owner();

            assert(
                0 <= l &&
                l <= r &&
                r <= size()
            );

            if (l == r) {
                return;
            }

            auto [a, bc] =
                owner_->split_root(
                    root_,
                    l
                );

            auto [b, c] =
                owner_->split_root(
                    bc,
                    r - l
                );

            owner_->toggle_reverse(b);

            root_ =
                owner_->merge_root(
                    owner_->merge_root(
                        a,
                        b
                    ),
                    c
                );
        }


        // ------------------------------------------------------------
        // split
        //
        // *this は空になる。
        // ------------------------------------------------------------

        std::pair<sequence, sequence>
        split(int k) {
            check_owner();

            assert(
                0 <= k &&
                k <= size()
            );

            auto [a, b] =
                owner_->split_root(
                    root_,
                    k
                );

            root_ = nil;

            return {
                sequence(owner_, a),
                sequence(owner_, b)
            };
        }


        // ------------------------------------------------------------
        // merge
        //
        // rhs を末尾に連結。
        // rhs は move-consume される。
        // ------------------------------------------------------------

        sequence&
        merge(sequence&& rhs) {
            check_owner();
            rhs.check_owner();

            assert(
                this != &rhs
            );

            assert(
                owner_ == rhs.owner_ &&
                "cannot merge sequences "
                "from different pools"
            );

            root_ =
                owner_->merge_root(
                    root_,
                    rhs.root_
                );

            rhs.root_ = nil;
            rhs.owner_ = nullptr;

            return *this;
        }


        // ------------------------------------------------------------
        // lower_bound
        //
        // ranges::lower_bound 相当。
        //
        // 列が
        // comp(proj(x_i), proj(x_j))
        // に関してソート済みであることを仮定。
        //
        // projection は列要素だけに適用する点も
        // std::ranges と同じ。
        // ------------------------------------------------------------

        template <
            class T,
            class Comp = std::ranges::less,
            class Proj = std::identity
        >
        int lower_bound(
            const T& value,
            Comp comp = {},
            Proj proj = {}
        ) {
            check_owner();

            int t = root_;
            int base = 0;
            int ans = size();

            while (t != nil) {
                owner_->push(t);

                int ls =
                    owner_->node_size(
                        owner_->nodes_[t].l
                    );

                int idx =
                    base + ls;

                if (
                    std::invoke(
                        comp,
                        std::invoke(
                            proj,
                            owner_->nodes_[t].val
                        ),
                        value
                    )
                ) {
                    base = idx + 1;
                    t = owner_->nodes_[t].r;

                } else {
                    ans = idx;
                    t = owner_->nodes_[t].l;
                }
            }

            return ans;
        }


        // ------------------------------------------------------------
        // upper_bound
        //
        // ranges::upper_bound 相当。
        // ------------------------------------------------------------

        template <
            class T,
            class Comp = std::ranges::less,
            class Proj = std::identity
        >
        int upper_bound(
            const T& value,
            Comp comp = {},
            Proj proj = {}
        ) {
            check_owner();

            int t = root_;
            int base = 0;
            int ans = size();

            while (t != nil) {
                owner_->push(t);

                int ls =
                    owner_->node_size(
                        owner_->nodes_[t].l
                    );

                int idx =
                    base + ls;

                if (
                    !std::invoke(
                        comp,
                        value,
                        std::invoke(
                            proj,
                            owner_->nodes_[t].val
                        )
                    )
                ) {
                    base = idx + 1;
                    t = owner_->nodes_[t].r;

                } else {
                    ans = idx;
                    t = owner_->nodes_[t].l;
                }
            }

            return ans;
        }
    };


private:

    int max_nodes_;

    std::vector<Node> nodes_;
    std::vector<int> free_;

    uint64_t rng_state_;


    // ------------------------------------------------------------
    // RNG
    // ------------------------------------------------------------

    static uint64_t default_seed() {
        return
            uint64_t(
                std::chrono::steady_clock::now()
                    .time_since_epoch()
                    .count()
            )
            ^
            uint64_t(
                reinterpret_cast<uintptr_t>(
                    &default_seed
                )
            );
    }


    uint64_t rng() {
        uint64_t z =
            (
                rng_state_
                += 0x9e3779b97f4a7c15ULL
            );

        z =
            (z ^ (z >> 30))
            * 0xbf58476d1ce4e5b9ULL;

        z =
            (z ^ (z >> 27))
            * 0x94d049bb133111ebULL;

        return
            z ^ (z >> 31);
    }


    // ------------------------------------------------------------
    // basic node utilities
    // ------------------------------------------------------------

    int node_size(int t) const {
        return t == nil
            ? 0
            : nodes_[t].sz;
    }


    bool higher(
        int a,
        int b
    ) const {
        if (
            nodes_[a].pri
            != nodes_[b].pri
        ) {
            return
                nodes_[a].pri
                > nodes_[b].pri;
        }

        // priority collision を完全に処理
        return a > b;
    }


    int new_node(S x) {
        int v;

        if (!free_.empty()) {
            v = free_.back();
            free_.pop_back();

            nodes_[v] =
                Node(
                    std::move(x),
                    rng()
                );

        } else {
            assert(
                static_cast<int>(
                    nodes_.size()
                )
                < max_nodes_
                &&
                "implicit_treap node pool exhausted"
            );

            v =
                static_cast<int>(
                    nodes_.size()
                );

            nodes_.emplace_back(
                std::move(x),
                rng()
            );
        }

        return v;
    }


    void release_node(int v) {
        assert(v != nil);
        free_.push_back(v);
    }


    // 部分木全体を freelist に返す。
    // lazy を push する必要はない。
    void release_tree(int root) {
        if (root == nil) {
            return;
        }

        std::vector<int> st{
            root
        };

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();

            if (nodes_[v].l != nil) {
                st.push_back(
                    nodes_[v].l
                );
            }

            if (nodes_[v].r != nil) {
                st.push_back(
                    nodes_[v].r
                );
            }

            free_.push_back(v);
        }
    }


    // ------------------------------------------------------------
    // aggregate
    // ------------------------------------------------------------

    S fwd(int t) const {
        return t == nil
            ? e()
            : nodes_[t].agg.fwd;
    }


    S bwd(int t) const {
        return t == nil
            ? e()
            : nodes_[t].agg.bwd;
    }


    void pull(int t) {
        Node& n =
            nodes_[t];

        n.sz =
            node_size(n.l)
            + 1
            + node_size(n.r);

        if constexpr (has_monoid) {
            n.agg.fwd =
                op(
                    op(
                        fwd(n.l),
                        n.val
                    ),
                    fwd(n.r)
                );

            n.agg.bwd =
                op(
                    op(
                        bwd(n.r),
                        n.val
                    ),
                    bwd(n.l)
                );
        }
    }


    // ------------------------------------------------------------
    // lazy
    //
    // composition(f, g) = f ∘ g
    // ACL と同じ順序。
    // ------------------------------------------------------------

    void apply_all(
        int t,
        const F& f
    ) {
        if (t == nil) {
            return;
        }

        if constexpr (has_lazy) {
            Node& n =
                nodes_[t];

            n.val =
                mapping(
                    f,
                    n.val
                );

            n.agg.fwd =
                mapping(
                    f,
                    n.agg.fwd
                );

            n.agg.bwd =
                mapping(
                    f,
                    n.agg.bwd
                );

            if (n.lazy.pending) {
                n.lazy.tag =
                    composition(
                        f,
                        n.lazy.tag
                    );

            } else {
                n.lazy.tag = f;
                n.lazy.pending = true;
            }
        }
    }


    // ------------------------------------------------------------
    // reverse
    // ------------------------------------------------------------

    void toggle_reverse(int t) {
        if (t == nil) {
            return;
        }

        Node& n =
            nodes_[t];

        std::swap(
            n.l,
            n.r
        );

        n.rev =
            !n.rev;

        if constexpr (has_monoid) {
            std::swap(
                n.agg.fwd,
                n.agg.bwd
            );
        }
    }


    // ------------------------------------------------------------
    // push
    // ------------------------------------------------------------

    void push(int t) {
        if (t == nil) {
            return;
        }

        Node& n =
            nodes_[t];

        if (n.rev) {
            toggle_reverse(n.l);
            toggle_reverse(n.r);

            n.rev = false;
        }

        if constexpr (has_lazy) {
            if (n.lazy.pending) {
                F f =
                    n.lazy.tag;

                apply_all(
                    n.l,
                    f
                );

                apply_all(
                    n.r,
                    f
                );

                n.lazy.pending = false;
                n.lazy.tag = id();
            }
        }
    }


    // ------------------------------------------------------------
    // split / merge core
    // ------------------------------------------------------------

    std::pair<int, int>
    split_root(
        int t,
        int k
    ) {
        if (t == nil) {
            return {
                nil,
                nil
            };
        }

        assert(
            0 <= k &&
            k <= node_size(t)
        );

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (k <= ls) {
            auto [a, b] =
                split_root(
                    nodes_[t].l,
                    k
                );

            nodes_[t].l = b;

            pull(t);

            return {
                a,
                t
            };

        } else {
            auto [a, b] =
                split_root(
                    nodes_[t].r,
                    k - ls - 1
                );

            nodes_[t].r = a;

            pull(t);

            return {
                t,
                b
            };
        }
    }


    int merge_root(
        int a,
        int b
    ) {
        if (a == nil) {
            return b;
        }

        if (b == nil) {
            return a;
        }

        if (higher(a, b)) {
            push(a);

            nodes_[a].r =
                merge_root(
                    nodes_[a].r,
                    b
                );

            pull(a);

            return a;

        } else {
            push(b);

            nodes_[b].l =
                merge_root(
                    a,
                    nodes_[b].l
                );

            pull(b);

            return b;
        }
    }


    // ------------------------------------------------------------
    // set / get
    // ------------------------------------------------------------

    void set_impl(
        int t,
        int p,
        S x
    ) {
        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (p < ls) {
            set_impl(
                nodes_[t].l,
                p,
                std::move(x)
            );

        } else if (p == ls) {
            nodes_[t].val =
                std::move(x);

        } else {
            set_impl(
                nodes_[t].r,
                p - ls - 1,
                std::move(x)
            );
        }

        pull(t);
    }


    S get_impl(
        int t,
        int p
    ) {
        while (true) {
            push(t);

            int ls =
                node_size(
                    nodes_[t].l
                );

            if (p < ls) {
                t =
                    nodes_[t].l;

            } else if (p == ls) {
                return
                    nodes_[t].val;

            } else {
                p -= ls + 1;
                t =
                    nodes_[t].r;
            }
        }
    }

	// ------------------------------------------------------------
	// to_vector
	//
	// subtree t の [l, r) を inorder で res に追加する。
	// ------------------------------------------------------------

	void to_vector_impl(
		int t,
		int l,
		int r,
		std::vector<S>& res
	) {
		if (
			t == nil ||
			l == r
		) {
			return;
		}

		assert(
			0 <= l &&
			l <= r &&
			r <= node_size(t)
		);

		push(t);

		int ls =
			node_size(
				nodes_[t].l
			);

		// 左部分木との共通部分
		if (l < ls) {
			to_vector_impl(
				nodes_[t].l,
				l,
				std::min(r, ls),
				res
			);
		}

		// 自分自身
		if (
			l <= ls &&
			ls < r
		) {
			res.push_back(
				nodes_[t].val
			);
		}

		// 右部分木との共通部分
		if (r > ls + 1) {
			int nl =
				std::max(
					0,
					l - ls - 1
				);

			int nr =
				r - ls - 1;

			to_vector_impl(
				nodes_[t].r,
				nl,
				nr,
				res
			);
		}
	}
    // ------------------------------------------------------------
    // prod
    // ------------------------------------------------------------

    S prod_impl(
        int t,
        int l,
        int r
    ) {
        if (l == r) {
            return e();
        }

        if (
            l == 0 &&
            r == node_size(t)
        ) {
            return
                nodes_[t].agg.fwd;
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        S res = e();

        if (l < ls) {
            res =
                op(
                    res,
                    prod_impl(
                        nodes_[t].l,
                        l,
                        std::min(r, ls)
                    )
                );
        }

        if (
            l <= ls &&
            ls < r
        ) {
            res =
                op(
                    res,
                    nodes_[t].val
                );
        }

        if (r > ls + 1) {
            int nl =
                std::max(
                    0,
                    l - ls - 1
                );

            int nr =
                r - ls - 1;

            res =
                op(
                    res,
                    prod_impl(
                        nodes_[t].r,
                        nl,
                        nr
                    )
                );
        }

        return res;
    }


    // ------------------------------------------------------------
    // point apply
    // ------------------------------------------------------------

    void apply_point_impl(
        int t,
        int p,
        const F& f
    ) {
        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (p < ls) {
            apply_point_impl(
                nodes_[t].l,
                p,
                f
            );

        } else if (p == ls) {
            // subtree 全体ではなく
            // この要素だけに mapping
            nodes_[t].val =
                mapping(
                    f,
                    nodes_[t].val
                );

        } else {
            apply_point_impl(
                nodes_[t].r,
                p - ls - 1,
                f
            );
        }

        pull(t);
    }


    // ------------------------------------------------------------
    // range apply
    // ------------------------------------------------------------

    void apply_range_impl(
        int t,
        int l,
        int r,
        const F& f
    ) {
        if (
            l == r ||
            t == nil
        ) {
            return;
        }

        if (
            l == 0 &&
            r == node_size(t)
        ) {
            apply_all(
                t,
                f
            );

            return;
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (l < ls) {
            apply_range_impl(
                nodes_[t].l,
                l,
                std::min(r, ls),
                f
            );
        }

        if (
            l <= ls &&
            ls < r
        ) {
            nodes_[t].val =
                mapping(
                    f,
                    nodes_[t].val
                );
        }

        if (r > ls + 1) {
            int nl =
                std::max(
                    0,
                    l - ls - 1
                );

            int nr =
                r - ls - 1;

            apply_range_impl(
                nodes_[t].r,
                nl,
                nr,
                f
            );
        }

        pull(t);
    }


    // ------------------------------------------------------------
    // max_right
    // ------------------------------------------------------------

    template <class G>
    int max_right_impl(
        int t,
        int l,
        S& sm,
        G& g
    ) {
        int n =
            node_size(t);

        if (
            t == nil ||
            l == n
        ) {
            return n;
        }

        // subtree 全体を一発で取れる場合
        if (l == 0) {
            S cand =
                op(
                    sm,
                    nodes_[t].agg.fwd
                );

            if (
                std::invoke(
                    g,
                    cand
                )
            ) {
                sm =
                    std::move(cand);

                return n;
            }
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (l < ls) {
            int x =
                max_right_impl(
                    nodes_[t].l,
                    l,
                    sm,
                    g
                );

            if (x < ls) {
                return x;
            }

            S cand =
                op(
                    sm,
                    nodes_[t].val
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return ls;
            }

            sm =
                std::move(cand);

            int y =
                max_right_impl(
                    nodes_[t].r,
                    0,
                    sm,
                    g
                );

            return
                ls + 1 + y;
        }


        if (l == ls) {
            S cand =
                op(
                    sm,
                    nodes_[t].val
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return ls;
            }

            sm =
                std::move(cand);

            int y =
                max_right_impl(
                    nodes_[t].r,
                    0,
                    sm,
                    g
                );

            return
                ls + 1 + y;
        }


        int y =
            max_right_impl(
                nodes_[t].r,
                l - ls - 1,
                sm,
                g
            );

        return
            ls + 1 + y;
    }


    // ------------------------------------------------------------
    // min_left
    // ------------------------------------------------------------

    template <class G>
    int min_left_impl(
        int t,
        int r,
        S& sm,
        G& g
    ) {
        int n =
            node_size(t);

        if (
            t == nil ||
            r == 0
        ) {
            return 0;
        }

        // subtree 全体
        if (r == n) {
            S cand =
                op(
                    nodes_[t].agg.fwd,
                    sm
                );

            if (
                std::invoke(
                    g,
                    cand
                )
            ) {
                sm =
                    std::move(cand);

                return 0;
            }
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (r > ls + 1) {
            int x =
                min_left_impl(
                    nodes_[t].r,
                    r - ls - 1,
                    sm,
                    g
                );

            if (x > 0) {
                return
                    ls + 1 + x;
            }

            S cand =
                op(
                    nodes_[t].val,
                    sm
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return
                    ls + 1;
            }

            sm =
                std::move(cand);

            return
                min_left_impl(
                    nodes_[t].l,
                    ls,
                    sm,
                    g
                );
        }


        if (r == ls + 1) {
            S cand =
                op(
                    nodes_[t].val,
                    sm
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return
                    ls + 1;
            }

            sm =
                std::move(cand);

            return
                min_left_impl(
                    nodes_[t].l,
                    ls,
                    sm,
                    g
                );
        }


        return
            min_left_impl(
                nodes_[t].l,
                r,
                sm,
                g
            );
    }


    // ------------------------------------------------------------
    // O(n) build
    //
    // priority から Cartesian Tree を構築。
    // ------------------------------------------------------------

    int build_from_vector(
        std::vector<S> values
    ) {
        if (values.empty()) {
            return nil;
        }

        int active =
            static_cast<int>(
                nodes_.size()
            )
            -
            static_cast<int>(
                free_.size()
            );

        assert(
            static_cast<int>(
                values.size()
            )
            <= max_nodes_ - active
            &&
            "implicit_treap node pool exhausted"
        );


        std::vector<int> ids;

        ids.reserve(
            values.size()
        );

        for (auto& x : values) {
            ids.push_back(
                new_node(
                    std::move(x)
                )
            );
        }


        std::vector<int> st;

        st.reserve(
            ids.size()
        );


        for (int v : ids) {
            int last = nil;

            while (
                !st.empty() &&
                higher(
                    v,
                    st.back()
                )
            ) {
                last =
                    st.back();

                st.pop_back();
            }

            nodes_[v].l =
                last;

            if (!st.empty()) {
                nodes_[st.back()].r =
                    v;
            }

            st.push_back(v);
        }


        int root =
            st.front();


        // post-order pull
        std::vector<int> order;

        order.reserve(
            ids.size()
        );

        std::vector<int> dfs{
            root
        };

        while (!dfs.empty()) {
            int v =
                dfs.back();

            dfs.pop_back();

            order.push_back(v);

            if (nodes_[v].l != nil) {
                dfs.push_back(
                    nodes_[v].l
                );
            }

            if (nodes_[v].r != nil) {
                dfs.push_back(
                    nodes_[v].r
                );
            }
        }


        for (
            auto it = order.rbegin();
            it != order.rend();
            ++it
        ) {
            pull(*it);
        }


        return root;
    }


public:

    // ------------------------------------------------------------
    // pool constructor
    // ------------------------------------------------------------

    explicit implicit_treap(
        int max_nodes,
        uint64_t seed = default_seed()
    )
        : max_nodes_(max_nodes),
          rng_state_(seed) {

        assert(
            max_nodes >= 0
        );

        nodes_.reserve(
            max_nodes_
        );

        free_.reserve(
            max_nodes_
        );
    }


    implicit_treap(
        const implicit_treap&
    ) = delete;

    implicit_treap&
    operator=(
        const implicit_treap&
    ) = delete;


    // ------------------------------------------------------------
    // sequence construction
    // ------------------------------------------------------------

    sequence make_sequence() {
        return
            sequence(
                this,
                nil
            );
    }


    sequence make_sequence(
        std::vector<S> values
    ) {
        return
            sequence(
                this,
                build_from_vector(
                    std::move(values)
                )
            );
    }


    sequence make_sequence(
        std::initializer_list<S> values
    ) {
        return
            make_sequence(
                std::vector<S>(
                    values
                )
            );
    }


    // 短い alias
    sequence make() {
        return
            make_sequence();
    }


    sequence make(
        std::vector<S> values
    ) {
        return
            make_sequence(
                std::move(values)
            );
    }


    sequence make(
        std::initializer_list<S> values
    ) {
        return
            make_sequence(values);
    }


    // ------------------------------------------------------------
    // pool-level merge
    //
    // a,b を両方 consume して新しい sequence を返す。
    // ------------------------------------------------------------

    sequence merge(
        sequence&& a,
        sequence&& b
    ) {
        assert(
            &a != &b
        );

        a.check_owner();
        b.check_owner();

        assert(
            a.owner_ == this &&
            b.owner_ == this &&
            "cannot merge sequences from different pools"
        );

        int ar =
            a.root_;

        int br =
            b.root_;

        a.root_ = nil;
        b.root_ = nil;

        a.owner_ = nullptr;
        b.owner_ = nullptr;

        return
            sequence(
                this,
                merge_root(
                    ar,
                    br
                )
            );
    }


    // ------------------------------------------------------------
    // pool-level split
    // ------------------------------------------------------------

    std::pair<sequence, sequence>
    split(
        sequence&& s,
        int k
    ) {
        s.check_owner();

        assert(
            s.owner_ == this
        );

        return
            s.split(k);
    }


    // ------------------------------------------------------------
    // pool information
    // ------------------------------------------------------------

    int capacity() const {
        return max_nodes_;
    }


    int allocated_nodes() const {
        return
            static_cast<int>(
                nodes_.size()
            )
            -
            static_cast<int>(
                free_.size()
            );
    }
};

// implicit_treap<S> pool(n);
// auto t=pool.make(vec);


// generated by ChatGPT outside of contest time.
namespace implicit_treap_detail {

template <class S>
S disabled_op(S, S) {
    std::abort();
}

template <class S>
S disabled_e() {
    std::abort();
}

template <class S, class F>
S disabled_mapping(F, S) {
    std::abort();
}

template <class F>
F disabled_composition(F, F) {
    std::abort();
}

template <class F>
F disabled_id() {
    std::abort();
}


// aggregate を使わないときは空クラス
template <class S, bool Enabled>
struct aggregate_storage {
    explicit aggregate_storage(const S&) {}
};

template <class S>
struct aggregate_storage<S, true> {
    S prod;

    explicit aggregate_storage(const S& x)
        : prod(x) {}
};


// lazy を使わないときは空クラス
template <class F, bool Enabled, F (*Id)()>
struct lazy_storage {
    lazy_storage() = default;
};

template <class F, F (*Id)()>
struct lazy_storage<F, true, Id> {
    F tag;
    bool pending = false;

    lazy_storage() : tag(Id()) {}
};

}  // namespace implicit_treap_detail


template <
    class S,

    S (*op)(S, S)
        = implicit_treap_detail::disabled_op<S>,

    S (*e)()
        = implicit_treap_detail::disabled_e<S>,

    class F = S,

    S (*mapping)(F, S)
        = implicit_treap_detail::disabled_mapping<S, F>,

    F (*composition)(F, F)
        = implicit_treap_detail::disabled_composition<F>,

    F (*id)()
        = implicit_treap_detail::disabled_id<F>
>
class implicit_treap {
    static constexpr int nil = -1;

    static constexpr bool op_given =
        op != implicit_treap_detail::disabled_op<S>;

    static constexpr bool e_given =
        e != implicit_treap_detail::disabled_e<S>;

    static constexpr bool mapping_given =
        mapping != implicit_treap_detail::disabled_mapping<S, F>;

    static constexpr bool composition_given =
        composition != implicit_treap_detail::disabled_composition<F>;

    static constexpr bool id_given =
        id != implicit_treap_detail::disabled_id<F>;

public:

    static constexpr bool has_monoid =
        op_given && e_given;

    static constexpr bool has_lazy =
        mapping_given && composition_given && id_given;

private:

    static_assert(
        op_given == e_given,
        "implicit_treap: op and e must be specified together"
    );

    static_assert(
        mapping_given == composition_given &&
        composition_given == id_given,
        "implicit_treap: mapping, composition and id "
        "must be specified together"
    );

    static_assert(
        !has_lazy || has_monoid,
        "implicit_treap: lazy action requires op/e"
    );


    using Agg =
        implicit_treap_detail::aggregate_storage<
            S, has_monoid
        >;

    using Lazy =
        implicit_treap_detail::lazy_storage<
            F, has_lazy, id
        >;


    struct Node {
        int l = nil;
        int r = nil;

        int sz = 1;

        uint64_t pri = 0;

        S val;

        [[no_unique_address]]
        Agg agg;

        [[no_unique_address]]
        Lazy lazy;

        Node(S x, uint64_t p)
            : pri(p),
              val(std::move(x)),
              agg(val),
              lazy() {}
    };


public:

    class sequence {
        friend class implicit_treap;

        implicit_treap* owner_ = nullptr;
        int root_ = nil;


        sequence(
            implicit_treap* owner,
            int root
        )
            : owner_(owner),
              root_(root) {}


        void check_owner() const {
            assert(owner_ != nullptr);
        }


        void release() {
            if (owner_ && root_ != nil) {
                owner_->release_tree(root_);
            }

            root_ = nil;
        }


    public:

        sequence() = default;


        sequence(const sequence&) = delete;
        sequence& operator=(const sequence&) = delete;


        sequence(sequence&& other) noexcept
            : owner_(other.owner_),
              root_(other.root_) {

            other.owner_ = nullptr;
            other.root_ = nil;
        }


        sequence& operator=(sequence&& other) noexcept {
            if (this == &other) {
                return *this;
            }

            release();

            owner_ = other.owner_;
            root_ = other.root_;

            other.owner_ = nullptr;
            other.root_ = nil;

            return *this;
        }


        ~sequence() {
            release();
        }


        // ------------------------------------------------------------
        // basic
        // ------------------------------------------------------------

        int size() const {
            check_owner();
            return owner_->node_size(root_);
        }


        bool empty() const {
            return size() == 0;
        }


        void clear() {
            check_owner();
            release();
        }


        // ------------------------------------------------------------
        // ACL: set / get
        // ------------------------------------------------------------

        void set(int p, S x) {
            check_owner();

            assert(
                0 <= p &&
                p < size()
            );

            owner_->set_impl(
                root_,
                p,
                std::move(x)
            );
        }


        S get(int p) {
            check_owner();

            assert(
                0 <= p &&
                p < size()
            );

            return owner_->get_impl(
                root_,
                p
            );
        }

		// ------------------------------------------------------------
	// to_vector
	//
	// to_vector()       : 列全体
	// to_vector(l, r)   : [l, r)
	//
	// 計算量:
	//   expected O(log n + (r - l))
	//   全体なら O(n)
	// ------------------------------------------------------------

	std::vector<S> to_vector() {
		check_owner();

		std::vector<S> res;
		res.reserve(size());

		owner_->to_vector_impl(
			root_,
			0,
			size(),
			res
		);

		return res;
	}


	std::vector<S> to_vector(int l, int r) {
		check_owner();

		assert(
			0 <= l &&
			l <= r &&
			r <= size()
		);

		std::vector<S> res;
		res.reserve(r - l);

		owner_->to_vector_impl(
			root_,
			l,
			r,
			res
		);

		return res;
	}

        // ------------------------------------------------------------
        // ACL: prod / all_prod
        // ------------------------------------------------------------

        S prod(int l, int r) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::prod requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= r &&
                    r <= size()
                );

                return owner_->prod_impl(
                    root_,
                    l,
                    r
                );
            }
        }


        S all_prod() const {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::all_prod requires op/e"
                );

                std::abort();

            } else {
                return root_ == nil
                    ? e()
                    : owner_->nodes_[root_].agg.prod;
            }
        }


        // ------------------------------------------------------------
        // ACL: apply
        // ------------------------------------------------------------

        void apply(int p, F f) {
            check_owner();

            if constexpr (!has_lazy) {
                assert(
                    has_lazy &&
                    "implicit_treap::apply requires "
                    "mapping/composition/id"
                );

                std::abort();

            } else {
                assert(
                    0 <= p &&
                    p < size()
                );

                owner_->apply_point_impl(
                    root_,
                    p,
                    f
                );
            }
        }


        void apply(int l, int r, F f) {
            check_owner();

            if constexpr (!has_lazy) {
                assert(
                    has_lazy &&
                    "implicit_treap::apply requires "
                    "mapping/composition/id"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= r &&
                    r <= size()
                );

                owner_->apply_range_impl(
                    root_,
                    l,
                    r,
                    f
                );
            }
        }


        // ------------------------------------------------------------
        // ACL: max_right
        // ------------------------------------------------------------

        template <class G>
        int max_right(int l, G g) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::max_right requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= l &&
                    l <= size()
                );

                S sm = e();

                assert(
                    std::invoke(g, sm)
                );

                if (l == size()) {
                    return size();
                }

                return owner_->max_right_impl(
                    root_,
                    l,
                    sm,
                    g
                );
            }
        }


        // ACL と同じ max_right<g>(l) 形式
        template <bool (*g)(S)>
        int max_right(int l) {
            return max_right(l, g);
        }


        // ------------------------------------------------------------
        // ACL: min_left
        // ------------------------------------------------------------

        template <class G>
        int min_left(int r, G g) {
            check_owner();

            if constexpr (!has_monoid) {
                assert(
                    has_monoid &&
                    "implicit_treap::min_left requires op/e"
                );

                std::abort();

            } else {
                assert(
                    0 <= r &&
                    r <= size()
                );

                S sm = e();

                assert(
                    std::invoke(g, sm)
                );

                if (r == 0) {
                    return 0;
                }

                return owner_->min_left_impl(
                    root_,
                    r,
                    sm,
                    g
                );
            }
        }


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


        // ------------------------------------------------------------
        // insert / erase
        // ------------------------------------------------------------

        void insert(int k, S x) {
            check_owner();

            assert(
                0 <= k &&
                k <= size()
            );

            int v =
                owner_->new_node(
                    std::move(x)
                );

            auto [a, b] =
                owner_->split_root(
                    root_,
                    k
                );

            root_ =
                owner_->merge_root(
                    owner_->merge_root(
                        a,
                        v
                    ),
                    b
                );
        }


        void erase(int k) {
            check_owner();

            assert(
                0 <= k &&
                k < size()
            );

            auto [a, bc] =
                owner_->split_root(
                    root_,
                    k
                );

            auto [b, c] =
                owner_->split_root(
                    bc,
                    1
                );

            assert(
                owner_->node_size(b) == 1
            );

            owner_->release_node(b);

            root_ =
                owner_->merge_root(
                    a,
                    c
                );
        }


        // ------------------------------------------------------------
        // split
        //
        // *this は空になる。
        // ------------------------------------------------------------

        std::pair<sequence, sequence>
        split(int k) {
            check_owner();

            assert(
                0 <= k &&
                k <= size()
            );

            auto [a, b] =
                owner_->split_root(
                    root_,
                    k
                );

            root_ = nil;

            return {
                sequence(owner_, a),
                sequence(owner_, b)
            };
        }


        // ------------------------------------------------------------
        // merge
        //
        // rhs を末尾に連結。
        // rhs は move-consume される。
        // ------------------------------------------------------------

        sequence&
        merge(sequence&& rhs) {
            check_owner();
            rhs.check_owner();

            assert(
                this != &rhs
            );

            assert(
                owner_ == rhs.owner_ &&
                "cannot merge sequences "
                "from different pools"
            );

            root_ =
                owner_->merge_root(
                    root_,
                    rhs.root_
                );

            rhs.root_ = nil;
            rhs.owner_ = nullptr;

            return *this;
        }


        // ------------------------------------------------------------
        // lower_bound
        //
        // ranges::lower_bound 相当。
        //
        // 列が
        // comp(proj(x_i), proj(x_j))
        // に関してソート済みであることを仮定。
        //
        // projection は列要素だけに適用する点も
        // std::ranges と同じ。
        // ------------------------------------------------------------

        template <
            class T,
            class Comp = std::ranges::less,
            class Proj = std::identity
        >
        int lower_bound(
            const T& value,
            Comp comp = {},
            Proj proj = {}
        ) {
            check_owner();

            int t = root_;
            int base = 0;
            int ans = size();

            while (t != nil) {
                owner_->push(t);

                int ls =
                    owner_->node_size(
                        owner_->nodes_[t].l
                    );

                int idx =
                    base + ls;

                if (
                    std::invoke(
                        comp,
                        std::invoke(
                            proj,
                            owner_->nodes_[t].val
                        ),
                        value
                    )
                ) {
                    base = idx + 1;
                    t = owner_->nodes_[t].r;

                } else {
                    ans = idx;
                    t = owner_->nodes_[t].l;
                }
            }

            return ans;
        }


        // ------------------------------------------------------------
        // upper_bound
        //
        // ranges::upper_bound 相当。
        // ------------------------------------------------------------

        template <
            class T,
            class Comp = std::ranges::less,
            class Proj = std::identity
        >
        int upper_bound(
            const T& value,
            Comp comp = {},
            Proj proj = {}
        ) {
            check_owner();

            int t = root_;
            int base = 0;
            int ans = size();

            while (t != nil) {
                owner_->push(t);

                int ls =
                    owner_->node_size(
                        owner_->nodes_[t].l
                    );

                int idx =
                    base + ls;

                if (
                    !std::invoke(
                        comp,
                        value,
                        std::invoke(
                            proj,
                            owner_->nodes_[t].val
                        )
                    )
                ) {
                    base = idx + 1;
                    t = owner_->nodes_[t].r;

                } else {
                    ans = idx;
                    t = owner_->nodes_[t].l;
                }
            }

            return ans;
        }
    };


private:

    int max_nodes_;

    std::vector<Node> nodes_;
    std::vector<int> free_;

    uint64_t rng_state_;


    // ------------------------------------------------------------
    // RNG
    // ------------------------------------------------------------

    static uint64_t default_seed() {
        return
            uint64_t(
                std::chrono::steady_clock::now()
                    .time_since_epoch()
                    .count()
            )
            ^
            uint64_t(
                reinterpret_cast<uintptr_t>(
                    &default_seed
                )
            );
    }


    uint64_t rng() {
        uint64_t z =
            (
                rng_state_
                += 0x9e3779b97f4a7c15ULL
            );

        z =
            (z ^ (z >> 30))
            * 0xbf58476d1ce4e5b9ULL;

        z =
            (z ^ (z >> 27))
            * 0x94d049bb133111ebULL;

        return
            z ^ (z >> 31);
    }


    // ------------------------------------------------------------
    // basic node utilities
    // ------------------------------------------------------------

    int node_size(int t) const {
        return t == nil
            ? 0
            : nodes_[t].sz;
    }


    bool higher(
        int a,
        int b
    ) const {
        if (
            nodes_[a].pri
            != nodes_[b].pri
        ) {
            return
                nodes_[a].pri
                > nodes_[b].pri;
        }

        // priority collision を完全に処理
        return a > b;
    }


    int new_node(S x) {
        int v;

        if (!free_.empty()) {
            v = free_.back();
            free_.pop_back();

            nodes_[v] =
                Node(
                    std::move(x),
                    rng()
                );

        } else {
            assert(
                static_cast<int>(
                    nodes_.size()
                )
                < max_nodes_
                &&
                "implicit_treap node pool exhausted"
            );

            v =
                static_cast<int>(
                    nodes_.size()
                );

            nodes_.emplace_back(
                std::move(x),
                rng()
            );
        }

        return v;
    }


    void release_node(int v) {
        assert(v != nil);
        free_.push_back(v);
    }


    // 部分木全体を freelist に返す。
    // lazy を push する必要はない。
    void release_tree(int root) {
        if (root == nil) {
            return;
        }

        std::vector<int> st{
            root
        };

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();

            if (nodes_[v].l != nil) {
                st.push_back(
                    nodes_[v].l
                );
            }

            if (nodes_[v].r != nil) {
                st.push_back(
                    nodes_[v].r
                );
            }

            free_.push_back(v);
        }
    }


    // ------------------------------------------------------------
    // aggregate
    // ------------------------------------------------------------

    S aggregate(int t) const {
        return t == nil
            ? e()
            : nodes_[t].agg.prod;
    }


    void pull(int t) {
        Node& n =
            nodes_[t];

        n.sz =
            node_size(n.l)
            + 1
            + node_size(n.r);

        if constexpr (has_monoid) {
            n.agg.prod =
                op(
                    op(
                        aggregate(n.l),
                        n.val
                    ),
                    aggregate(n.r)
                );
        }
    }


    // ------------------------------------------------------------
    // lazy
    //
    // composition(f, g) = f ∘ g
    // ACL と同じ順序。
    // ------------------------------------------------------------

    void apply_all(
        int t,
        const F& f
    ) {
        if (t == nil) {
            return;
        }

        if constexpr (has_lazy) {
            Node& n =
                nodes_[t];

            n.val =
                mapping(
                    f,
                    n.val
                );

            n.agg.prod =
                mapping(
                    f,
                    n.agg.prod
                );

            if (n.lazy.pending) {
                n.lazy.tag =
                    composition(
                        f,
                        n.lazy.tag
                    );

            } else {
                n.lazy.tag = f;
                n.lazy.pending = true;
            }
        }
    }


    // ------------------------------------------------------------
    // push
    // ------------------------------------------------------------

    void push(int t) {
        if constexpr (has_lazy) {
            if (t == nil) {
                return;
            }

            Node& n =
                nodes_[t];

            if (n.lazy.pending) {
                F f =
                    n.lazy.tag;

                apply_all(
                    n.l,
                    f
                );

                apply_all(
                    n.r,
                    f
                );

                n.lazy.pending = false;
                n.lazy.tag = id();
            }
        }
    }


    // ------------------------------------------------------------
    // split / merge core
    // ------------------------------------------------------------

    std::pair<int, int>
    split_root(
        int t,
        int k
    ) {
        if (t == nil) {
            return {
                nil,
                nil
            };
        }

        assert(
            0 <= k &&
            k <= node_size(t)
        );

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (k <= ls) {
            auto [a, b] =
                split_root(
                    nodes_[t].l,
                    k
                );

            nodes_[t].l = b;

            pull(t);

            return {
                a,
                t
            };

        } else {
            auto [a, b] =
                split_root(
                    nodes_[t].r,
                    k - ls - 1
                );

            nodes_[t].r = a;

            pull(t);

            return {
                t,
                b
            };
        }
    }


    int merge_root(
        int a,
        int b
    ) {
        if (a == nil) {
            return b;
        }

        if (b == nil) {
            return a;
        }

        if (higher(a, b)) {
            push(a);

            nodes_[a].r =
                merge_root(
                    nodes_[a].r,
                    b
                );

            pull(a);

            return a;

        } else {
            push(b);

            nodes_[b].l =
                merge_root(
                    a,
                    nodes_[b].l
                );

            pull(b);

            return b;
        }
    }


    // ------------------------------------------------------------
    // set / get
    // ------------------------------------------------------------

    void set_impl(
        int t,
        int p,
        S x
    ) {
        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (p < ls) {
            set_impl(
                nodes_[t].l,
                p,
                std::move(x)
            );

        } else if (p == ls) {
            nodes_[t].val =
                std::move(x);

        } else {
            set_impl(
                nodes_[t].r,
                p - ls - 1,
                std::move(x)
            );
        }

        pull(t);
    }


    S get_impl(
        int t,
        int p
    ) {
        while (true) {
            push(t);

            int ls =
                node_size(
                    nodes_[t].l
                );

            if (p < ls) {
                t =
                    nodes_[t].l;

            } else if (p == ls) {
                return
                    nodes_[t].val;

            } else {
                p -= ls + 1;
                t =
                    nodes_[t].r;
            }
        }
    }

	// ------------------------------------------------------------
	// to_vector
	//
	// subtree t の [l, r) を inorder で res に追加する。
	// ------------------------------------------------------------

	void to_vector_impl(
		int t,
		int l,
		int r,
		std::vector<S>& res
	) {
		if (
			t == nil ||
			l == r
		) {
			return;
		}

		assert(
			0 <= l &&
			l <= r &&
			r <= node_size(t)
		);

		push(t);

		int ls =
			node_size(
				nodes_[t].l
			);

		// 左部分木との共通部分
		if (l < ls) {
			to_vector_impl(
				nodes_[t].l,
				l,
				std::min(r, ls),
				res
			);
		}

		// 自分自身
		if (
			l <= ls &&
			ls < r
		) {
			res.push_back(
				nodes_[t].val
			);
		}

		// 右部分木との共通部分
		if (r > ls + 1) {
			int nl =
				std::max(
					0,
					l - ls - 1
				);

			int nr =
				r - ls - 1;

			to_vector_impl(
				nodes_[t].r,
				nl,
				nr,
				res
			);
		}
	}
    // ------------------------------------------------------------
    // prod
    // ------------------------------------------------------------

    S prod_impl(
        int t,
        int l,
        int r
    ) {
        if (l == r) {
            return e();
        }

        if (
            l == 0 &&
            r == node_size(t)
        ) {
            return
                nodes_[t].agg.prod;
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        S res = e();

        if (l < ls) {
            res =
                op(
                    res,
                    prod_impl(
                        nodes_[t].l,
                        l,
                        std::min(r, ls)
                    )
                );
        }

        if (
            l <= ls &&
            ls < r
        ) {
            res =
                op(
                    res,
                    nodes_[t].val
                );
        }

        if (r > ls + 1) {
            int nl =
                std::max(
                    0,
                    l - ls - 1
                );

            int nr =
                r - ls - 1;

            res =
                op(
                    res,
                    prod_impl(
                        nodes_[t].r,
                        nl,
                        nr
                    )
                );
        }

        return res;
    }


    // ------------------------------------------------------------
    // point apply
    // ------------------------------------------------------------

    void apply_point_impl(
        int t,
        int p,
        const F& f
    ) {
        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (p < ls) {
            apply_point_impl(
                nodes_[t].l,
                p,
                f
            );

        } else if (p == ls) {
            // subtree 全体ではなく
            // この要素だけに mapping
            nodes_[t].val =
                mapping(
                    f,
                    nodes_[t].val
                );

        } else {
            apply_point_impl(
                nodes_[t].r,
                p - ls - 1,
                f
            );
        }

        pull(t);
    }


    // ------------------------------------------------------------
    // range apply
    // ------------------------------------------------------------

    void apply_range_impl(
        int t,
        int l,
        int r,
        const F& f
    ) {
        if (
            l == r ||
            t == nil
        ) {
            return;
        }

        if (
            l == 0 &&
            r == node_size(t)
        ) {
            apply_all(
                t,
                f
            );

            return;
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (l < ls) {
            apply_range_impl(
                nodes_[t].l,
                l,
                std::min(r, ls),
                f
            );
        }

        if (
            l <= ls &&
            ls < r
        ) {
            nodes_[t].val =
                mapping(
                    f,
                    nodes_[t].val
                );
        }

        if (r > ls + 1) {
            int nl =
                std::max(
                    0,
                    l - ls - 1
                );

            int nr =
                r - ls - 1;

            apply_range_impl(
                nodes_[t].r,
                nl,
                nr,
                f
            );
        }

        pull(t);
    }


    // ------------------------------------------------------------
    // max_right
    // ------------------------------------------------------------

    template <class G>
    int max_right_impl(
        int t,
        int l,
        S& sm,
        G& g
    ) {
        int n =
            node_size(t);

        if (
            t == nil ||
            l == n
        ) {
            return n;
        }

        // subtree 全体を一発で取れる場合
        if (l == 0) {
            S cand =
                op(
                    sm,
                    nodes_[t].agg.prod
                );

            if (
                std::invoke(
                    g,
                    cand
                )
            ) {
                sm =
                    std::move(cand);

                return n;
            }
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (l < ls) {
            int x =
                max_right_impl(
                    nodes_[t].l,
                    l,
                    sm,
                    g
                );

            if (x < ls) {
                return x;
            }

            S cand =
                op(
                    sm,
                    nodes_[t].val
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return ls;
            }

            sm =
                std::move(cand);

            int y =
                max_right_impl(
                    nodes_[t].r,
                    0,
                    sm,
                    g
                );

            return
                ls + 1 + y;
        }


        if (l == ls) {
            S cand =
                op(
                    sm,
                    nodes_[t].val
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return ls;
            }

            sm =
                std::move(cand);

            int y =
                max_right_impl(
                    nodes_[t].r,
                    0,
                    sm,
                    g
                );

            return
                ls + 1 + y;
        }


        int y =
            max_right_impl(
                nodes_[t].r,
                l - ls - 1,
                sm,
                g
            );

        return
            ls + 1 + y;
    }


    // ------------------------------------------------------------
    // min_left
    // ------------------------------------------------------------

    template <class G>
    int min_left_impl(
        int t,
        int r,
        S& sm,
        G& g
    ) {
        int n =
            node_size(t);

        if (
            t == nil ||
            r == 0
        ) {
            return 0;
        }

        // subtree 全体
        if (r == n) {
            S cand =
                op(
                    nodes_[t].agg.prod,
                    sm
                );

            if (
                std::invoke(
                    g,
                    cand
                )
            ) {
                sm =
                    std::move(cand);

                return 0;
            }
        }

        push(t);

        int ls =
            node_size(
                nodes_[t].l
            );

        if (r > ls + 1) {
            int x =
                min_left_impl(
                    nodes_[t].r,
                    r - ls - 1,
                    sm,
                    g
                );

            if (x > 0) {
                return
                    ls + 1 + x;
            }

            S cand =
                op(
                    nodes_[t].val,
                    sm
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return
                    ls + 1;
            }

            sm =
                std::move(cand);

            return
                min_left_impl(
                    nodes_[t].l,
                    ls,
                    sm,
                    g
                );
        }


        if (r == ls + 1) {
            S cand =
                op(
                    nodes_[t].val,
                    sm
                );

            if (
                !std::invoke(
                    g,
                    cand
                )
            ) {
                return
                    ls + 1;
            }

            sm =
                std::move(cand);

            return
                min_left_impl(
                    nodes_[t].l,
                    ls,
                    sm,
                    g
                );
        }


        return
            min_left_impl(
                nodes_[t].l,
                r,
                sm,
                g
            );
    }


    // ------------------------------------------------------------
    // O(n) build
    //
    // priority から Cartesian Tree を構築。
    // ------------------------------------------------------------

    int build_from_vector(
        std::vector<S> values
    ) {
        if (values.empty()) {
            return nil;
        }

        int active =
            static_cast<int>(
                nodes_.size()
            )
            -
            static_cast<int>(
                free_.size()
            );

        assert(
            static_cast<int>(
                values.size()
            )
            <= max_nodes_ - active
            &&
            "implicit_treap node pool exhausted"
        );


        std::vector<int> ids;

        ids.reserve(
            values.size()
        );

        for (auto& x : values) {
            ids.push_back(
                new_node(
                    std::move(x)
                )
            );
        }


        std::vector<int> st;

        st.reserve(
            ids.size()
        );


        for (int v : ids) {
            int last = nil;

            while (
                !st.empty() &&
                higher(
                    v,
                    st.back()
                )
            ) {
                last =
                    st.back();

                st.pop_back();
            }

            nodes_[v].l =
                last;

            if (!st.empty()) {
                nodes_[st.back()].r =
                    v;
            }

            st.push_back(v);
        }


        int root =
            st.front();


        // post-order pull
        std::vector<int> order;

        order.reserve(
            ids.size()
        );

        std::vector<int> dfs{
            root
        };

        while (!dfs.empty()) {
            int v =
                dfs.back();

            dfs.pop_back();

            order.push_back(v);

            if (nodes_[v].l != nil) {
                dfs.push_back(
                    nodes_[v].l
                );
            }

            if (nodes_[v].r != nil) {
                dfs.push_back(
                    nodes_[v].r
                );
            }
        }


        for (
            auto it = order.rbegin();
            it != order.rend();
            ++it
        ) {
            pull(*it);
        }


        return root;
    }


public:

    // ------------------------------------------------------------
    // pool constructor
    // ------------------------------------------------------------

    explicit implicit_treap(
        int max_nodes,
        uint64_t seed = default_seed()
    )
        : max_nodes_(max_nodes),
          rng_state_(seed) {

        assert(
            max_nodes >= 0
        );

        nodes_.reserve(
            max_nodes_
        );

        free_.reserve(
            max_nodes_
        );
    }


    implicit_treap(
        const implicit_treap&
    ) = delete;

    implicit_treap&
    operator=(
        const implicit_treap&
    ) = delete;


    // ------------------------------------------------------------
    // sequence construction
    // ------------------------------------------------------------

    sequence make_sequence() {
        return
            sequence(
                this,
                nil
            );
    }


    sequence make_sequence(
        std::vector<S> values
    ) {
        return
            sequence(
                this,
                build_from_vector(
                    std::move(values)
                )
            );
    }


    sequence make_sequence(
        std::initializer_list<S> values
    ) {
        return
            make_sequence(
                std::vector<S>(
                    values
                )
            );
    }


    // 短い alias
    sequence make() {
        return
            make_sequence();
    }


    sequence make(
        std::vector<S> values
    ) {
        return
            make_sequence(
                std::move(values)
            );
    }


    sequence make(
        std::initializer_list<S> values
    ) {
        return
            make_sequence(values);
    }


    // ------------------------------------------------------------
    // pool-level merge
    //
    // a,b を両方 consume して新しい sequence を返す。
    // ------------------------------------------------------------

    sequence merge(
        sequence&& a,
        sequence&& b
    ) {
        assert(
            &a != &b
        );

        a.check_owner();
        b.check_owner();

        assert(
            a.owner_ == this &&
            b.owner_ == this &&
            "cannot merge sequences from different pools"
        );

        int ar =
            a.root_;

        int br =
            b.root_;

        a.root_ = nil;
        b.root_ = nil;

        a.owner_ = nullptr;
        b.owner_ = nullptr;

        return
            sequence(
                this,
                merge_root(
                    ar,
                    br
                )
            );
    }


    // ------------------------------------------------------------
    // pool-level split
    // ------------------------------------------------------------

    std::pair<sequence, sequence>
    split(
        sequence&& s,
        int k
    ) {
        s.check_owner();

        assert(
            s.owner_ == this
        );

        return
            s.split(k);
    }


    // ------------------------------------------------------------
    // pool information
    // ------------------------------------------------------------

    int capacity() const {
        return max_nodes_;
    }


    int allocated_nodes() const {
        return
            static_cast<int>(
                nodes_.size()
            )
            -
            static_cast<int>(
                free_.size()
            );
    }
};

// implicit_treap<S> pool(n);
// auto t=pool.make(vec);