void quick_sort(int a[], int l, int r)
{
if (l >= r) return;
int x=a[(l+r)/2], i = l - 1, j = r + 1, q[100010], k = 0;
while (i < j)
{
do i++; while (a[i] < x);
do j–; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}