#include <iostream>
#include <fstream>

using namespace std;

bool readArray(istream& s, double* &a, int &n);
bool writeArray(ostream& s, const double *a, int n);

void insertSort(double *a, int n);

int main() {
    ifstream f("input.txt");
    if (!f.is_open()) {
        cerr << "Could not open an input file" << endl;
        return (-1);
    }
    
    double *a; int n;
    if (!readArray(f, a, n)) {
        cerr << "Could not read an input file" << endl;
        return (-1);
    }
    f.close();
    
    insertSort(a, n);
    
    cout << "Sorted array:" << endl;
    writeArray(cout, a, n);
    
    ofstream g("output.txt");
    if (!g.is_open()) {
        cerr << "Could not open an output file" << endl;
        return (-1);
    }
    
    writeArray(g, a, n);
    g.close();
    
    return 0;
}
    
bool readArray(istream& s, double* &a, int &n) {
    if (!(s >> n))
        return false;
    a = new double[n];
    for (int i = 0; i < n; ++i) {
        if (!(s >> a[i]))
            return false;
    }
    return true;
}

bool writeArray(ostream& s, const double *a, int n) {
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            // Print a delimiter
            if (i%5 == 0) {
                s << endl;
            } else {
                s << ' ';
            }
        }
        s << a[i];
    }
    s << endl;
    return true;
}

void insertSort(double *a, int n) {
    int k = 1;
    while (k < n) {
        // Invariant: a[0] <= a[1] <= ... <= a[k-1]
        double x = a[k];
        if (x < a[k-1]) {
            int i = k;
            while (i > 0 && x < a[i-1]) {
                a[i] = a[i-1];
                --i;
            }
            a[i] = x;            
        }
        ++k;
    }
}