void merge_sort(int a[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(a, l, mid), merge_sort(a, mid + 1, r); int q[100010], i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] <= a[j]) q[k++] = a[i++]; else q[k++] = a[j++]; } while (i <= mid) q[k++] = a[i++]; while (j <= r) q[k++] = a[j++]; for (int i = l, j = 0; j < k; j++, i++) a[i] = q[j]; }