#include <bits/stdc++.h>
using namespace std;

void adjustHeap(int* arr, int n, int i){
    int mx = i;
    int l = 2*i;
    int r = 2*i + 1;
    if(l <= n && arr[l] > arr[mx]) mx = l;
    if(r <= n && arr[r] > arr[mx]) mx = r;
    if(mx != i){
        swap(arr[i], arr[mx]);
        adjustHeap(arr, n, mx);
    }
}

void Heap_sort(int* arr, int n){
    for(int i = n/2; i >= 1; i--){
        adjustHeap(arr, n, i);
    }
    for(int i = n; i >= 1; i--){
        swap(arr[i], arr[1]);
        adjustHeap(arr, i-1, 1);
    }
}

int main() {
    int n;
    int maxn = 50005;
    ...