1. #include<iostream>
2. using namespace std;
3.  
4. void insertion(int a[], int n)
5. {
6.     for(int i=1; i<n; i++)
7.     {
8.         int ele= a[i];
9.         int j=i-1;
10.         while(a[j]>ele && j>=0)
11.         {
12.             a[j+1]=a[j];
13.             --j;
14.         }
15.         a[j+1]= ele;
16.     }
17. }
18.  
19. void selection(int a[], int n)
20. {
21.     for(int i=0; i<n-1; i++)
22.     {
23.         int min= i;
24.         for(int j=i+1; j<n; j++)
25.         {
26.             if(a[j]<a[min])
27.             {
28.                 min=j;
29.             }
30.         }
31.         swap(a[min], a[i]);
32.     }
33. }
34.  
35.  
36. void merge(int a[], int left, int mid, int right)
37. {
38.     int a1= mid-left+1, a2= right-mid;
39.  
40.     int templeft[a1], tempright[a2];
41.  
42.     for(int i=0; i<a1; i++)
43.     {
44.         templeft[i]= a[i+left];
45.     }
46.  
47.     for(int i=0; i<a2; i++)
48.     {
49.         tempright[i]= a[mid+1+i];
50.     }
51.  
52.     int idxleft=0, idxright=0, idxarr= left;
53.  
54.     while(idxleft<a2)
55.     {
56.         if(templeft[idxleft]<tempright[idxright])
57.         {
58.             a[idxarr]= templeft[idxleft];
59.             idxleft++;
60.         }
61.         else
62.         {
63.             a[idxarr]= tempright[idxright];
64.             idxright++;
65.         }
66.         idxarr++;
67.     }
68.  
69.     while(idxleft<a1)
70.     {
71.         a[idxarr]= templeft[idxleft];
72.         idxleft++, idxarr++;
73.     }
74.  
75.     while(idxright<a2)
76.     {
77.         a[idxarr]= tempright[idxright];
78.         idxright++, idxarr++;
79.     }
80. }
81.  
82.  
83. void mergesort(int a[], int left, int right)
84. {
85.     if(left>=right)
86.     {
87.         return;
88.     }
89.     int mid= (left+right)/2;
90.     mergesort(a, left, mid);
91.     mergesort(a, mid+1, right);
92.     merge(a, left, mid, right);
93. }
94.  
95.  
96. int partition(int a[], int low, int high)
97. {
98.     int pivot= a[high];
99.     int i= low-1;
100.     for(int x= low; x<high; x++)
101.     {
102.         if(a[x]<pivot)
103.         {
104.             i++;
105.             swap(a[i], a[x]);
106.         }
107.     }
108.     swap(a[i+1], a[high]);
109.     return i+1;
110. }
111.  
112.  
113. void quicksort(int a[], int low, int high)
114. {
115.     if(low>=high)
116.     return;
117.  
118.     int pi= partition(a, low, high);
119.     quicksort(a, low, pi-1);
120.     quicksort(a, pi+1, high);
121.  
122. }
123.  
124.  
125. void heapify(int a[], int n, int i)
126. {
127.     int largest=i;
128.     int l= 2*i+1;
129.     int r= 2*i+2;
130.     if(l>a[largest])
131.     {
132.         largest=l;
133.     }
134.     if(r>a[largest])
135.     {
136.         largest=r;
137.     }
138.     if(largest != i)
139.     {
140.         swap(a[largest], a[i]);
141.         heapify(a, n, largest);
142.     }
143.    
144. }
145.  
146.  
147. void heapsort(int a[], int n)
148. {
149.     for(int i=n/2-1; i>=0; i--)
150.     {
151.         heapify(a, n, i);
152.     }
153.  
154.     for(int i= n-1; i>0; i--)
155.     {
156.         swap(a[0], a[i]);
157.         heapify(a, i, 0);
158.     }
159. }
160.  
161.  
162. int main()
163. {
164.     int n;
165.     cin>>n;
166.     int a[n];
167.     for(int i=0; i<n; i++)
168.     {
169.         cin>>a[i];
170.     }
171.     heapsort(a, n);
172.     for(int x=0; x<n; x++)
173.     {
174.         cout<<a[x]<<" ";
175.     }
176. }