#include <iostream>

using namespace std;

const int N = 100010;

int q[N];  // 定义数组

void quick_sort(int q[], int l, int r) {  // 定义快速排序函数
    if (l >= r) return;  // 如果左边界大于等于右边界，直接返回

    int i = l - 1, j = r + 1, x = q[l + r >> 1];  // 初始化左右指针和中间值
    while (i < j){  // 当左指针小于右指针时循环
        do i++; while (q[i] < x);  // 从左向右找到第一个 q[i] >= x 的位置
        do j--; while (q[j] > x);  // 从右向左找到第一个 q[j] <= x 的位置
        if (i < j) swap(q[i], q[j]);  // 如果左指针不大于右指针，则交换 q[i] 和 q[j]
    }

    quick_sort(q, l, j);  // 对左半部分继续排序
    quick_sort(q, j + 1, r);  // 对右半部分继续排序
}

int main(){
    int n;
    scanf("%d", &n);  // 输入数组长度

  &nb...