#undef _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;


template<size_t len>
class Rolling_Hash_Base : public array<uint64_t, len>{
private:
    static constexpr uint64_t add(uint64_t a, uint64_t b){
        a+=b+1;
        a = (a&mod) + (a>>61);
        return a-1;
    }
    static constexpr uint64_t sub(uint64_t a, uint64_t b){
        return add(a, mod-b);
    }
    static constexpr uint64_t modmul(uint64_t a, uint64_t b){
        uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
        uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
        uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
        ret = (ret & mod) + (ret>>61);
        ret = (ret & mod) + (ret>>61);
        return ret-1;
    }
    static const array<uint64_t, len> base;
    static array<uint64_t, len>const& get_base_pow(int exp){
        assert(exp>=0);
        static vector<array<uint64_t, len> > base_pow;
        if((int)base_pow.size() <= exp){
            if(base_pow.empty()){
                base_pow.reserve(1001);
                base_pow.emplace_back();
                for(auto &e:base_pow.back()) e = 1;
            }
            for(int it=base_pow.size(); it<exp+1000;++it){
                base_pow.push_back(base_pow.back());
                auto &e = base_pow.back();
                for(size_t i=0;i<len;++i){
                    e[i] = modmul(e[i], base[i]);
                }
            }
        }
        return base_pow[exp];
    }

public:
    static constexpr uint64_t mod = (1ull<<61) - 1;

    Rolling_Hash_Base() : array<uint64_t, len>{} {};
    Rolling_Hash_Base(Rolling_Hash_Base const&o) = default;
    Rolling_Hash_Base& operator=(Rolling_Hash_Base const&o) = default;

    static array<uint64_t, len> gen_base(){
        //seed_seq seed{(uint32_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(), (uint32_t)random_device()(), (uint32_t)4730921};
        seed_seq seed{(uint32_t)492214};
        mt19937 rng(seed);
        array<uint64_t, len> ret;
        for(auto &e:ret) e = uniform_int_distribution<uint64_t>(0, mod-1)(rng);
        return ret;
    }
    static vector<Rolling_Hash_Base> hashify(string const&s){
        vector<Rolling_Hash_Base> ret;
        ret.reserve(s.size()+1);
        ret.push_back(Rolling_Hash_Base());
        for(char const&e:s){
            ret.push_back(ret.back() + e);
        }
        return ret;
    }

    template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
    Rolling_Hash_Base& operator+=(T const&o){
        for(size_t i=0;i<len;++i){
            (*this)[i] = add(modmul((*this)[i], base[i]), static_cast<uint64_t>(o));
        }
        ++length;
        return *this;
    }
    template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
    Rolling_Hash_Base operator+(T const&o)const{
        Rolling_Hash_Base ret(*this);
        ret+=o;
        return ret;
    }
    Rolling_Hash_Base& operator-=(Rolling_Hash_Base const&o){
        assert(length >= o.length);
        auto const&base_pow = get_base_pow(length - o.length);
        //cerr << length << " - " << o.length << "\n";
        for(size_t i=0;i<len;++i){
            (*this)[i] = sub((*this)[i], modmul(o[i], base_pow[i]));
        }
        length-=o.length;
        return *this;
    }
    Rolling_Hash_Base operator-(Rolling_Hash_Base const&o)const{
        Rolling_Hash_Base ret(*this);
        ret-=o;
        return ret;
    }

    size_t length = 0;
};
template<size_t len>
const array<uint64_t, len> Rolling_Hash_Base<len>::base = Rolling_Hash_Base<len>::gen_base();

using Rolling_Hash = Rolling_Hash_Base<2>;


class Treap {
public:
    struct Node {
        Node*l = nullptr, *r = nullptr;
        uint64_t y;
        int x;
        Node() : y(0), x(-1) {}
        Node(int x_, uint64_t y_) : y(y_),  x(x_) {}
    };
    Treap(int n, function<uint64_t(int)> seed) : roots(n), nodes(n){
        for(int i=0;i<n;++i){
            nodes[i] = Node(i, seed(i));
            roots[i] = &nodes[i];
        }
    }

    int merge(int const i, int const j){
        roots[i] = merge(roots[i], roots[j]);
        roots[j] = nullptr;
        free_roots.push_back(j);
        return i;
    }
    pair<int, int> split(int const i, int const x){
        assert(!free_roots.empty());
        const int j = free_roots.back(); free_roots.pop_back();
        tie(roots[i], roots[j]) = split(roots[i], x);
        return make_pair(i, j);
    }
    Rolling_Hash hash(int i){
        Rolling_Hash ret;
        hash(roots[i], ret);
        return ret;
    }

    uint64_t get_calls() const { return calls; }
    void reset_calls() { calls = 0; }

private:
    pair<Node*, Node*> split(Node *u, int x){
        ++calls;
        if(!u) return {nullptr, nullptr};
        if(x <= u->x){
            auto tmp = split(u->l, x);
            u->l = tmp.second;
            return {tmp.first, u};
        } else {
            auto tmp = split(u->r, x);
            u->r = tmp.first;
            return {u, tmp.second};
        }
    }
    Node* join(Node *l, Node *r){
        ++calls;
        if(!l) return r;
        if(!r) return l;
        if(l->y < r->y){
            l->r = join(l->r, r);
            return l;
        } else {
            r->l = join(l, r->l);
            return r;
        }
    }
    Node* merge(Node *u, Node *v){
        ++calls;
        if(!u) return v;
        if(!v) return u;
        if(u->y > v->y) swap(u, v);
        auto tmp = split(v, u->x);
        u->l = merge(u->l, tmp.first);
        u->r = merge(u->r, tmp.second);
        return u;
    }
    void hash(Node*u, Rolling_Hash &h){
        if(u){
            if(u->l) assert(u->y <= u->l->y);
            if(u->r) assert(u->y <= u->r->y);
            hash(u->l, h);
            h += u->x;
            hash(u->r, h);
        }
    }

    vector<int> free_roots;
    vector<Node*> roots;
    vector<Node> nodes;
    uint64_t calls = 0;
};

struct Sparse_Sement_tree{
    struct Node{
        Node *l, *r;
        Node() : l(nullptr), r(nullptr) {}
    };

    Sparse_Sement_tree(int n_, function<uint64_t(int)>) : n(n_), roots(n){
        for(int i=0;i<n;++i){
            roots[i] = build(i, 0, n-1);
        }
    }

    int merge(int const i, int const j){
        roots[i] = merge(roots[i], roots[j]);
        roots[j] = nullptr;
        free_roots.push_back(j);
        return i;
    }
    pair<int, int> split(int const i, int const x){
        assert(!free_roots.empty());
        const int j = free_roots.back(); free_roots.pop_back();
        tie(roots[i], roots[j]) = split(roots[i], 0, n-1, x);
        return make_pair(i, j);
    }


    Rolling_Hash hash(int i){
        Rolling_Hash ret;
        hash(roots[i], 0, n-1, ret);
        return ret;
    }


    uint64_t get_calls() const { return calls; }
    void reset_calls() { calls = 0; }

private:
    Node* build(int x, int l, int r){
        ++calls;
        if(x < l || x > r) return nullptr;
        Node* ret = new Node();
        if(l != r){
            ret->l = build(x, l, (r+l)/2);
            ret->r = build(x, (r+l)/2+1, r);
        }
        return ret;
    }
    Node* merge(Node*u, Node*v){
        ++calls;
        if(!u) return v;
        if(!v) return u;
        u->l = merge(u->l, v->l);
        u->r = merge(u->r, v->r);
        delete v;
        return u;
    }
    pair<Node*, Node*> split(Node*u, int l, int r, int x){
        ++calls;
        if(!u) return {nullptr, nullptr};
        if(l == r){
            if(l<x) return {u, nullptr};
            return {nullptr, u};
        }
        const int m = (l+r)/2;
        auto v = new Node();
        if(x <= m){
            auto tmp = split(u->l, l, m, x);
            u->l = tmp.second;
            v->l = tmp.first;
            return {v, u};
        } else {
            auto tmp = split(u->r, m+1, r, x);
            u->r = tmp.first;
            v->r = tmp.second;
            return {u, v};
        }
    }
    void hash(Node*u, int l, int r, Rolling_Hash &h){
        if(!u) return;
        if(l == r){
            h += l;
        } else {
            hash(u->l, l, (l+r)/2, h);
            hash(u->r, (l+r)/2+1, r, h);
        }
    }

    int n;
    vector<int> free_roots;
    vector<Node*> roots;
    uint64_t calls = 0;
};


template<typename T>
void test_1(const int n, const int iterations, const bool do_hash){
    mt19937 rng(1234);
    auto get_rand = [&](int l, int r){
        return uniform_int_distribution<int>(l, r)(rng);
    }; (void)get_rand;
    Rolling_Hash expected_total_hash;
    uint64_t calls = 0, operations = 0;
    for(int trial=0;trial<iterations;++trial){
        mt19937 tree_rng(trial);
        Rolling_Hash total_hash;
        T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
        auto add_hash = [&](int i){
            if(do_hash){
                auto ha = tree.hash(i);
                for(auto const&e:ha) total_hash += e;
            }
        };

        vector<int> roots(n, 0);
        iota(roots.begin(), roots.end(), 0);
        while(roots.size() > 1){
            const int m = roots.size();
            const int k = m/2;
            for(int i = 0;i<k;++i){
                roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
                add_hash(roots[i]);
            }
            roots.erase(roots.begin() + m-k, roots.end());
        }
        //cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
        if(trial > 0){
            assert(total_hash == expected_total_hash);
        }
        expected_total_hash = total_hash;
        calls += tree.get_calls();
    }
    //const double avg_calls = calls/(double) iterations;
    // cerr << "Test 1: " << n << " : " << avg_calls << "\n";
    // if(do_hash) cerr << "   hash: " << expected_total_hash[0] << "\n";
    cerr << "   calls / operation: " << calls / (double) operations << "\n";
}
template<typename T>
void test_batch_1(){
    cerr << "==== " << typeid(T).name() << " ====\n";
    for(int k = 6; k<15; ++k){
        const int n = 1<<k;
        test_1<T>(n, 10, k <= 8);
    }
}

template<typename T>
void test_2(const int N, const int iterations, const bool do_hash){
    const int sqrt_n = sqrtl(N);
    const int n = sqrt_n * sqrt_n;
    mt19937 rng(1234);
    auto get_rand = [&](int l, int r){
        return uniform_int_distribution<int>(l, r)(rng);
    }; (void)get_rand;
    Rolling_Hash expected_total_hash;
    uint64_t calls = 0, operations = 0;
    for(int trial=0;trial<iterations;++trial){
        mt19937 tree_rng(trial);
        Rolling_Hash total_hash;
        T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
        auto add_hash = [&](int i){
            if(do_hash){
                auto ha = tree.hash(i);
                for(auto const&e:ha) total_hash += e;
            }
        };
        // setup single set
        int root = 0;
        for(int i=1;i<n;++i){
            root = tree.merge(root, i), ++operations;
            add_hash(root);
        }
        for(int it=0;it<sqrt_n;++it){
            // build sqrt_n blocks of size sqrt_n
            vector<int> roots(sqrt_n);
            for(int i=sqrt_n-1; i>0; --i){
                tie(root, roots[i]) = tree.split(root, i*sqrt_n), ++operations;
                add_hash(roots[i]);
            }
            roots[0] = root;
            // then merge blocks again
            while(roots.size() > 1){
                const int m = roots.size();
                const int k = m/2;
                for(int i = 0;i<k;++i){
                    roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
                    add_hash(i);
                }
                roots.erase(roots.begin() + m-k, roots.end());
            }
        }
        //cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
        if(trial > 0){
            assert(total_hash == expected_total_hash);
        }
        expected_total_hash = total_hash;
        calls += tree.get_calls();
    }
    const double avg_calls = calls/(double) iterations;
    cerr << "Test 2: " << n << " : " << fixed << avg_calls << "\n";
    if(do_hash) cerr << "   hash: " << expected_total_hash[0] << "\n";
    cerr << "   calls / operation: " << calls / (double) operations << "\n";
}
template<typename T>
void test_batch_2(){
    cerr << "==== " << typeid(T).name() << " ====\n";
    for(int k = 5; k<16; ++k){
        const int n = 1<<k;
        test_2<T>(n, 10, k <= 8);
    }
}

int main() {
	cerr.rdbuf(cout.rdbuf());
    //test_batch_1<Treap>();
    //test_batch_1<Sparse_Sement_tree>();
    test_batch_2<Treap>();
    test_batch_2<Sparse_Sement_tree>();

    return 0;
}