#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

template<typename T, typename Comp = std::less<T>>
using OrdTreeBase = __gnu_pbds::tree<T, __gnu_pbds::null_type, Comp,
                                     __gnu_pbds::rb_tree_tag,
                                     __gnu_pbds::tree_order_statistics_node_update>;


template<typename T, typename Comp = std::less<T>>
struct OrderedSet : public OrdTreeBase<T, Comp>
{
    using Base = OrdTreeBase<T, Comp>;
    
    OrderedSet(const auto &...pack)
        : Base(pack...) { }
    
    size_t count_less(const auto &key) const {
        return this->order_of_key(key);
    }
    
    size_t count_less_equal(const auto &key) const {
        return upper_bound_with_order(key).second;
    }
    
    size_t count_greater(const auto &key) const {
        return this->size() - count_less_equal(key);
    }
    
    size_t count_equal(const auto &key) const {
        return count_less_equal(key) - count_less(key);
    }
    
    template<typename Compare = Comp>
    std::pair<typename Base::const_iterator, size_t>
    lower_bound_with_order(const auto &key) const
    {
        auto prev = this->m_p_head;
        auto curr = this->m_p_head->m_p_parent;
        size_t order{};
        while (curr != 0)
            if (Compare()(curr->m_value, key)) {
                order += curr->m_metadata;
                if ((curr = curr->m_p_right))
                    order -= curr->m_metadata;
            } else {
                prev = curr;
                curr = curr->m_p_left;
            }
        return std::make_pair(prev, order);
    }
    
    template<typename Compare = Comp>
    std::pair<typename Base::const_iterator, size_t>
    upper_bound_with_order(const auto &key) const
    {
        auto prev = this->m_p_head;
        auto curr = this->m_p_head->m_p_parent;
        size_t order{};
        while (curr != 0)
            if (Compare()(key, curr->m_value)) {
                prev = curr;
                curr = curr->m_p_left;
            } else {
                order += curr->m_metadata;
                if ((curr = curr->m_p_right))
                    order -= curr->m_metadata;
            }
        return std::make_pair(prev, order);
    }
    
};

const int INF = (int)1e9+7;

template<typename T, typename Comp>
void test(const char * name) {
    printf("--------------------------------------\n");
    printf("test: %s\n", name);
    std::vector<T> vec;
    for (int i = 0; i < 10; i += 2)
        vec.push_back(i);
    OrderedSet<T, Comp> set(vec.begin(), vec.end());
    printf("set:");
    for (auto it : set)
        printf(" %d", it);
    printf("\n");
    printf("lower_bound_with_order:\n");
    for (int i = -1; i < 10; i++) {
        auto [it, order] = set.lower_bound_with_order(i);
        if (it != set.end())
            assert(set.order_of_key(*it) == order);
        else
            assert(order == set.size());
        int value = (it == set.end()) ? INF : *it;
        printf("\t%d: lb = %d, order = %lu\n", i, value, order);
    }
    printf("upper_bound_with_order:\n");
    for (int i = -1; i < 10; i++) {
        auto [it, order] = set.upper_bound_with_order(i);
        if (it != set.end())
            assert(set.order_of_key(*it) == order);
        else
            assert(order == set.size());
        int value = (it == set.end()) ? INF : *it;
        printf("\t%d: up = %d, order = %lu\n", i, value, order);
    }
}

int main() {
    test<int, std::less<int>>("test sorted");
    test<int, std::greater<int>>("test reversed");
}

test: test sorted
set: 0 2 4 6 8
lower_bound_with_order:
        -1: lb = 0, order = 0
        0: lb = 0, order = 0
        1: lb = 2, order = 1
        2: lb = 2, order = 1
        3: lb = 4, order = 2
        4: lb = 4, order = 2
        5: lb = 6, order = 3
        6: lb = 6, order = 3
        7: lb = 8, order = 4
        8: lb = 8, order = 4
        9: lb = 1000000007, order = 5
upper_bound_with_order:
        -1: up = 0, order = 0
        0: up = 2, order = 1
        1: up = 2, order = 1
        2: up = 4, order = 2
        3: up = 4, order = 2
        4: up = 6, order = 3
        5: up = 6, order = 3
        6: up = 8, order = 4
        7: up = 8, order = 4
        8: up = 1000000007, order = 5
        9: up = 1000000007, order = 5

test: test reversed
set: 8 6 4 2 0
lower_bound_with_order:
        -1: lb = 1000000007, order = 5
        0: lb = 0, order = 4
        1: lb = 0, order = 4
        2: lb = 2, order = 3
        3: lb = 2, order = 3
        4: lb = 4, order = 2
        5: lb = 4, order = 2
        6: lb = 6, order = 1
        7: lb = 6, order = 1
        8: lb = 8, order = 0
        9: lb = 8, order = 0
upper_bound_with_order:
        -1: up = 1000000007, order = 5
        0: up = 1000000007, order = 5
        1: up = 0, order = 4
        2: up = 0, order = 4
        3: up = 2, order = 3
        4: up = 2, order = 3
        5: up = 4, order = 2
        6: up = 4, order = 2
        7: up = 6, order = 1
        8: up = 6, order = 1
        9: up = 8, order = 0