// min leftist tree
// T must define <
// M: the size of the heap
template<typename T,size_t M,typename Cmp=less<T>>
struct Leftist
{
    static Cmp cmp;
    T val[M];
    int l[M],r[M],d[M];
    int nn; // number of node
    void init() { nn=0; }
    // using val to build a leftist tree
    // return the id of the root
    int build(int n,T val_[]) 
    {
        queue<int> qu;
        for(int i=1;i<=n;i++) qu.push(i);
        int u,v;
        while(qu.size()>1)
        {
            u=qu.front(); qu.pop();
            v=qu.front(); qu.pop();
            merge(u,v); qu.push(u);
        }
        return qu.front();
    }
    int newtree(T v)
    {
        val[++nn]=v;
        r[nn]=l[nn]=d[nn]=0;
        return nn;
    }
    void merge(int &x,int y) // merge tree x and tree y
    {
        if(!x||!y) return x=x+y,void();
        if(cmp(val[y],val[x])) swap(x,y);
        merge(r[x],y);
        if(d[l[x]]<d[r[x]]) swap(l[x],r[x]);
        d[x]=d[r[x]]+1;
    }
    void insert(int &rt,T v) // insert v into tree rt
    { merge(rt,newtree(v)); }
    T top(int rt) { return val[rt]; }
    void pop(int &rt)
    { int rs=r[rt]; rt=l[rt]; merge(rt,rs); }
};