#ifndef __HEAP__
#define __HEAP__
#ifdef __cplusplus



#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
struct SHEAP{
    int *heap;
    int num;
    SHEAP(int size){num=0;heap=new int[size];}
    inline void push(int x){
        heap[++num]=x;
        register int i=num,k;
        while(i>1){
            k=i>>1;
            if(heap[k]<=heap[i])    return;
            swap(heap[k],heap[i]);
            i=k;
        }
    }
    
    inline int pop(){
        int ans=heap[1];
        heap[1]=heap[num--];
        register int i=1,k;
        while((i<<1)<=num){
            k=i<<1;
            if(k<num&&heap[k]>heap[k|1])    k|=1;
            if(heap[i]<=heap[k])    return ans;
            swap(heap[i],heap[k]);
            i=k;
        }
        return ans;
    }
};


struct BHEAP{
    int *heap;
    int num;
    BHEAP(int size){num=0;heap=new int[size];}
    inline void push(int x){
        heap[++num]=x;
        register int i=num,k;
        while(i>1){
            k=i>>1;
            if(heap[k]>=heap[i])    return;
            swap(heap[k],heap[i]);
            i=k;
        }
    }
    
    inline int pop(){
        int ans=heap[1];
        heap[1]=heap[num--];
        register int i=1,k;
        while((i<<1)<=num){
            k=i<<1;
            if(k<num&&heap[k]<heap[k|1])    k|=1;
            if(heap[i]>=heap[k])    return ans;
            swap(heap[i],heap[k]);
            i=k;
        }
        return ans;
    }
};



#endif
#endif