#include<iostream>
using namespace std;
#define MAX 0x0fffffff
#define parent(i) (i)>>1
#define left(i) (i)<<1
#define right(i) ((i)<<1)+1
int a[MAX];
int len;
int size;//堆中元素长度
void maxheapify(int i)//维护最大堆的性质 O(lgn)
{ int l=left(i);
int r=right(i);
int large=i;
if(l<=size&&a[l]>a[i])
large=l;
if(r<=size&&a[r]>a[large])
large=r;
if(large!=i)
{ int tmp=a[i];
a[i]=a[large];
a[large]=tmp;
maxheapify(large);
}
}
void build()//建堆 O(nlgn)
{ size=len;
int i;
for(i=(len>>1);i>=1;i--)
{ maxheapify(i);
}
}
int heap_max_heapify()//维护最大优先级，返回最大元素
{ int maxx;
maxx=a[1];
a[1]=a[size];
size--;
maxheapify(1);
return maxx;
}
void heap_change_key(int i,int key)//将堆中元素i置为key
{ if(key<a[i])
{ a[i]=key;
maxheapify(i);
}
else
{ a[i]=key;
while(i>1&&a[i]>a[parent(i)])
{ int tmp=a[i];
a[i]=a[parent(i)];
a[parent(i)]=tmp;
}
}
}
void heapsort()//堆排序 O(nlgn)
{ build();
int i;
for(i=len;i>=2;i--)
{ int tmp=a[i];
a[i]=a[1];
a[1]=tmp;
size--;
maxheapify(1);
}
}//heapsort之后，size为1；
void max_heap_insert(int key)//插入值为key的元素
{ size++;
a[size]=key;
heap_change_key(size,key);
return ;
}
int main()
{ scanf("%d",&len);
int i;
for(i=1;i<=len;i++)
{ scanf("%d",&a[i]);
}
build();
heapsort();
size=len;
for(i=size;i>=1;i--)
printf("%d ",a[i]);
max_heap_insert(100);
len=size;
heapsort();
for(i=len;i>=1;i--)
printf("%d ",a[i]);
size=len;
system("pause");
return 0;
}