1. #include <iostream>
2. using namespace std;
3.  
4. int findNextR(int l, int size, int *arr) {
5.         for (int i = l; i < size; ++i) {
6.                 if (arr[i] < 0)
7.                         return i;
8.         }
9.         return size - 1;
10. }
11.  
12. int partition(int l, int r, int *arr) {
13.         long pivot = arr[(l + r) / 2];
14.         while (l <= r) {
15.                 while (arr[r] > pivot)
16.                         r--;
17.                 while (arr[l] < pivot)
18.                         l++;
19.                 if (l <= r) {
20.                         long tmp = arr[r];
21.                         arr[r] = arr[l];
22.                         arr[l] = tmp;
23.                         l++;
24.                         r--;
25.                 }
26.         }
27.         return l;
28. }
29. void quickSort(int size, int *arr) {
30.         int l = 0;
31.         int r = size - 1;
32.         int q, i = 0;
33.         int tmpr = r;
34.         while (true) {
35.                 i--;
36.                 while (l < tmpr) {
37.                         q = partition(l, tmpr, arr);
38.                         arr[tmpr] = -arr[tmpr];
39.                         tmpr = q - 1;
40.                         ++i;
41.                 }
42.                 if (i < 0)
43.                         break;
44.                 l++;
45.                 tmpr = findNextR(l, size, arr);
46.                 arr[tmpr] = -arr[tmpr];
47.         }
48. }
49.  
50. int main() {
51.         int size;
52.         cin >> size;
53.         int *arr = new int[size];
54.  
55.         quickSort(size, arr);
56.  
57.         return 0;
58. }