1. #include <iostream>
2. #include <vector>
3.  
4. using namespace std;
5.  
6. // int swap(int &a, int& b){
7. //     int c = a;
8. //     a = b;
9. //     return b = c;
10. // }
11.  
12. int sorted[1000] = {0};
13.  
14. void minElement (vector <int> v, int& vitrimin, int& min){
15.     min = 9999;
16.     for (int i = 0; i < v.size(); i++){
17.         if (min > v[i] && sorted[v[i]] == 0){
18.             min = v[i];
19.             vitrimin = i;
20.         }
21.     }
22.     sorted[min] = 1;
23. }
24.  
25. void maxElement (vector <int> v, int& vitrimax, int& max){
26.     max = -9999;
27.     for (int i = 0; i < v.size(); i++){
28.         if (max < v[i] && sorted[v[i]] == 0){
29.             max = v[i];
30.             vitrimax = i;
31.         }
32.     }
33.     sorted[max] = 1;
34. }
35.  
36.  
37. // 1 4 7 -> 4 1 7 -> 1 4 7
38. int main() {
39.     int n;
40.     cin>>n;
41.     int min;
42.     int max;
43.     vector <int> v;
44.     int vitrimax;
45.     int vitrimin;
46.     for (int i = 0; i < n; i++){
47.         int value;
48.         cin>>value;
49.         v.push_back(value);
50.     }
51.     for (int i = 0; i < n; i++) {
52.         if ((i + 1) % 2 != 0) {
53.             // cout << i << " ";
54.             minElement(v, vitrimin, min);
55.             // cout << min << " " << vitrimin;
56.             while (min - 1 != vitrimin) {
57.                 swap(v[vitrimin - 1], v[vitrimin]);
58.                 vitrimin--;
59.             }
60.         }
61.         else {
62.             maxElement(v, vitrimax, max);
63.             // cout << min << " " << vitrimin;
64.             while (max - 1 != vitrimax && vitrimax <= n) {
65.                 swap(v[vitrimax + 1], v[vitrimax]);
66.                 vitrimax++;
67.             }
68.         }
69.         // else {
70.         //     maxElement(v, vitrimax, max);
71.         //     while (max - 1 != vitrimax) {
72.         //         if (v[vitrimax + 1] < v[vitrimax]) {
73.         //                             swap(v[vitrimax + 1], v[vitrimax]);
74.         //         }
75.         //         vitrimax++;
76.         // }
77.         // }
78.     }
79.     // for (auto x : v) {
80.     //     cout << x << " ";
81.     // }
82.     // 3 1 4 2
83.                 for (auto x : v) {
84.                 cout << x << " ";
85.             }
86.    
87. }
88.