// T must define <
// min heap
// M: max size of heap
template<typename T,size_t M,typename Cmp=less<T>>
struct Heap
{
	static Cmp cmp;
	T h[M+1];
	int n;
	void init() { n=0; }
	void init(T h_[],int n_) // h[0~n-1]
	{
		n=n_;
		for(int i=1;i<=n;i++) h[i]=h_[i-1];
		for(int i=n/2;i;i--) sink(i); // O(n)
	}
	void push(T x) { h[++n]=x; swim(n); }
	T pop() { T res=h[1]; h[1]=h[n--]; sink(1); return res; }
	T top() { return h[1]; } // check n>=1
    int size() { return n; }
    bool empty() { return n==0; }
	/* Helper ----------------------------------- */
	void sink(int p)
	{
		int q=p<<1; T x=h[p];
		while(q<=n)
		{
			if(q<n&&cmp(h[q+1],h[q])) q++;
			if(!cmp(h[q],x)) break; // h[q]>=x
			h[p]=h[q]; p=q; q=p<<1;
		}
		h[p]=x;
	}
	void swim(int p)
	{
		int q=p>>1; T x=h[p];
		while(q&&cmp(x,h[q]))
		{ h[p]=h[q]; p=q; q=p>>1; }
		h[p]=x;
	}
};

	/* Debug ------------------------------------ 
	   T need to define function
	   ostream& operator<<(ostream& out, T rhs);  */
	void show()
	{
		cout<<"Heap:-------------------------\n";
		for(int i=1,j=1;i<=n;i++)
		{
			cout<<h[i]<<'\t';
			if(i==j) { j=j<<1|1; cout<<'\n'; }
		}
		cout<<"------------------------------\n\n";
	}

// T must define < 
// M: max size of heap
template<typename T,size_t M,typename Cmp=less<>>
struct Heap
{
	typedef pair<T,int> PTI;
	T h[M+1];
	int key[M+1]; // key[i] is unique and in [0~M-1] 
	int pos[M];   // position of elememt which key is i
	int n;        // number of node in the current heap
	int nk;       // number of key
	Cmp cmp;
	void init(int nk_=0)
	{ 
		n=0; nk=nk_; 
		for(int i=0;i<nk;i++) pos[i]=-1;  
	}
	void init(T h_[],int key_[],int n_,int nk_=0) // h[0~n-1]
	{
		n=n_; nk=nk_;
		for(int i=1;i<=n;i++) h[i]=h_[i-1];
        for(int i=0;i<nk;i++) pos[i]=-1;
		for(int i=1;i<=n;i++) 
			key[i]=key_[i-1],pos[key[i]]=i;
		for(int i=n/2;i;i--) sink(i); // O(n)
	}
	void push(T x,int k)
	{ h[++n]=x; key[n]=k; pos[k]=n; swim(n); }
	PTI pop()
	{
		T res=h[1]; int k=key[1]; 
		h[1]=h[n]; key[1]=key[n--]; pos[key[1]]=1;
		sink(1);
		return {res,k};
	}
	// decrease key to val
	void dec(int k,T val) // check key in [0~n-1]
	{
		int p=pos[k];
		T oldval=h[p];
		if(cmp(al,oldval)) { h[p]=val; swim(p); }
	}
    // remove element which key is k
    T remove(int k) // check k is exist
    {
        int p=pos[k]; T val=h[p];
        h[p]=h[n]; key[p]=key[n--]; pos[key[p]]=p;
        sink(p);
        return val;
    }
    bool contain(int k) { return pos[k]!=-1; }
    T get(int k) { return h[pos[k]]; }
    int size() { return n; }
    bool empty() { return n==0; }
	/* Helper ----------------------------------- */
	void sink(int p)
	{
		int q=p<<1; T x=h[p]; int k=key[p];
		while(q<=n)
		{
			if(q<n&&cmp(h[q+1],h[q])) q++;
			if(!cmp(h[q],x)) break; // h[q]>=x
			h[p]=h[q]; key[p]=key[q]; pos[key[p]]=p;
			p=q; q=p<<1;
		}
		h[p]=x; key[p]=k; pos[k]=p;
	}
	void swim(int p)
	{
		int q=p>>1; T x=h[p]; int k=key[p];
		while(q&&cmp(x,h[q]))
		{ 
			h[p]=h[q]; key[p]=key[q]; pos[key[p]]=p;
			p=q; q=p>>1;
		}
		h[p]=x; key[p]=k; pos[k]=p;
	}
};

	/* Debug ------------------------------------ 
	   T need to define function
	   ostream& operator<<(ostream& out, T rhs);  */
	void show()
	{
		cout<<"Heap:-------------------------\n";
		for(int i=1,j=1;i<=n;i++)
		{
			cout<<'('<<h[i]<<','<<key[i]<<")\t";
			if(i==j) { j=j<<1|1; cout<<'\n'; }
		}
		cout<<"\npos:";
		for(int i=0;i<nk;i++)
			cout<<pos[i]<<' ';
		cout<<'\n';
		cout<<"------------------------------\n\n";
	}