#include<algorithm>
using namespace std;

#define DIM 16001

int n,heap[DIM];

inline int father(int nod){
    
    return nod/2;}

inline int lson(int nod){
    
    return 2*nod;}
    
inline int rson(int nod){
    
    return 2*nod+1;}

void sift(int n,int k){
    int son;
    
    do{
        if(lson(k)<=n){
            son=lson(k);
            if(rson(k)<=n&&heap[rson(k)]>son)
                son=rson(k);
            if(heap[son]<=heap[k])
                son=0;}
        if(son){
            swap(heap[son],heap[k]);
            k=son;}}
    while(son);}

void percolate(int n,int k){
    int key;
    
    for(key=heap[k]; k>1&&key>heap[father(k)]; k=father(k))
        heap[k]=heap[father(k)];
    heap[k]=key;}

void build(){
    int i;
    
    for(i=n/2; i>0; --i)
        sift(n,i);}
        
void cut(int k){
    
    heap[k]=heap[n--];
    if(k>1&&heap[k]>father(k))
        percolate(n,k);
    else
        sift(n,k);}
        
void insert(int key){
    
    heap[++n]=key;
    percolate(n,n);}
    
void hsort(){
    int i;
        
    for(i=n; i>1; --i){
        swap(heap[n],heap[i]);
        sift(i-1,1);}}

int main(){
    
    freopen("heap.in","r",stdin);
    freopen("heap.out","w",stdout);
    
    return 0;}