#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005
template<typename T>
struct DefaultMaxCmp {
    bool operator()(const T& a, const T& b) const {
        return a > b;
    }
};

template<typename T>
struct DefaultMinCmp {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

int parent(const int & f){
    return f>>1;
}
int leftchild(const int & f){
    return f<<1;
}
int rightchild(const int & f){
    return (f<<1)+1;
}
template<typename T, typename Compare = DefaultMinCmp<T>>
struct heap{
    T a[MAXN];
    int len;
    Compare comp;
    
    heap() : len(0) {
        memset(a, 0, sizeof(a));
    }
    heap(const Compare& cmp) : len(0), comp(cmp) {
        memset(a, 0, sizeof(a));
    }
    ~heap(){
    	clear();
	}
	void clear(){
		while(!empty()) pop();
		return;
	}
    void heap_swap(const int & i,const int & j){
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
        return;
    }
    
    int size(){
        return len;
    }
    
    bool empty(){
        return len==0;
    }
    
    T top(){
        if(len) return a[1];
        else return T(); 
    }
    
    void heapifyup(int f){
        while(f>1 && comp(a[f], a[parent(f)])){
            heap_swap(f,parent(f));
            f=parent(f);
        }	
        return;
    }
    
    void heapifydown(int f){
        while(f<=len){
            int maxs=f,left=leftchild(maxs),right=rightchild(maxs);
            if(left<=len && comp(a[left],a[maxs])) maxs=left;
            if(right<=len && comp(a[right],a[maxs])) maxs=right;
            if(maxs==f) break;
            heap_swap(f,maxs),f=maxs;
        }
    }
    
    bool pop(const int & f=1){
        if(len){
            heap_swap(1,len);
            len--;
            if(len>0){
                heapifydown(1);
            }
        }
        else return 0;
        return 1;
    }
    
    bool push(const T & value){
        if(len+1==MAXN) return false;
        a[++len]=value;
        heapifyup(len);
        return true;
    }
};
template<typename T, bool (*cmp)(const T&, const T&) = DefaultMinCmp<T>().operator()>
struct heap_func_ptr{
    T a[MAXN];
    int len;
    
    heap_func_ptr(){
        memset(a, 0, sizeof(a));
        len = 0;
    }
    
    void heap_swap(const int & i,const int & j){
        T t=a[i];
        a[i]=a[j];
        a[j]=t;
        return;
    }
    
    int size(){
        return len;
    }
    
    bool empty(){
        return len==0;
    }
    
    T top(){
        if(len) return a[1];
        else return T();
    }
    
    void heapifyup(int f){
        while(f>1&&cmp(a[f],a[parent(f)])){
            heap_swap(f,parent(f));
            f=parent(f);
        }	
        return;
    }
    
    void heapifydown(int f){
        while(f<=len){
            int maxs=f,left=leftchild(maxs),right=rightchild(maxs);
            if(left<=len && cmp(a[left],a[maxs])) maxs=left;
            if(right<=len && cmp(a[right],a[maxs])) maxs=right;
            if(maxs==f) break;
            heap_swap(f,maxs),f=maxs;
        }
    }
    
    bool pop(const int & f=1){
        if(len){
            heap_swap(1,len);
            len--;
            if(len>0){
                heapifydown(1);
            }
        }
        else return 0;
        return 1;
    }
    
    bool push(const T & value){
        if(len+1==MAXN) return false;
        a[++len]=value;
        heapifyup(len);
        return true;
    }
};