HỌC TIN CÙNG THỦ KHOA

Mời các bạn download tại: Click here

#include <bits/stdc++.h>
using namespace std;
#define BUG(x) {cerr << #x << " = " << x <<endl;}
#define PR(x,a,b) {cerr << #x << " = "; for(int i = a; i <= b; i++) cerr << x[i] << ' '; cerr << endl;}
#define NMAX 10007
int n;
int a[NMAX];
void read() {
    cin >> n;
    for (int i = 1; i<=n; i++) {
        cin >> a[i];
    }
}
#define oo 1000000007
void init() {
    // coding continue
    a[0] = -oo;
}
int bs (int L, int R, int x) {
    int mid = (L+R)/2;

    if (a[mid] <= x && x <= a[mid+1])
        return mid;
    else /// x <= a[mid] hoặc x >= a[mid+1]
        if (x <= a[mid]) /// a[L] <= ... <= x <= a[mid] <= ... <= a[R]
            return bs(L, mid, x);
            else /// x >= a[mid+1]
                 /// a[L] <= ... <= a[mid+1] <= x <= ... <= a[R]
                 return bs(mid+1, R, x);
}
void insertion() {
    int k;
    /// a[1] <= a[2] <= ... <= a[k] <= a[i] <= a[k+1] ... <= a[i-1]         a[i]
    int x;
    for (int i=2; i <= n; i++) {
        k = bs(0, i-1, a[i]);
        x = a[i];
        for (int j = i-1; j >= k+1; j--)
            a[j+1] = a[j];
        a[k+1] = x;
    }
}
void solve() {
    insertion();

    for (int i = 1; i<=n; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
}

void write() {
    // coding continue
}
int main() {
    //freopen("*.INP","r",stdin);
    //freopen("*.OUT","w",stdout);
    read();
    init();
    solve();
    write();
    return 0;
}