#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 insertionSort(double *a, int n);

int main() {
    ifstream f("input.txt");    // Open the input file
    if (!f.is_open()) {
        cerr << "Could not open an input file" << endl;
        return (-1);
    }
    
    double *a; int n;
    if (!readArray(f, a, n)) {  // Read an array from the file
        cerr << "Could not read an input file" << endl;
        return (-1);
    }
    f.close();                  // Close the input file
    
    insertionSort(a, n);        // Sort the array
    
    cout << "Sorted array:" << endl;
    writeArray(cout, a, n);     // Print the sorted array to console
    
    ofstream g("output.txt");   // Open the output file
    if (!g.is_open()) {
        cerr << "Could not open an output file" << endl;
        return (-1);
    }
    
    writeArray(g, a, n);    // Write the sorted array to the output file
    g.close();              // Close the output file
    
    delete[] a;             // Release the array memory

    return 0;
}
    
// Read an array from the input stream
bool readArray(istream& s, double* &a, int &n) {
    // The first element in the file is the length of the array
    if (!(s >> n))
        return false;

    a = new double[n];      // Allocate memory for the array
    for (int i = 0; i < n; ++i) {
        if (!(s >> a[i]))   // Read the i-th element of the array
            return false;
    }
    return true;
}

// Write an array to the output stream
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;  // New line after every five elements,
            } else {
                s << ' ';   // otherwise, write a space
            }
        }
        s << a[i];          // Write the i-th element of the array
    }
    s << endl;
    return true;
}

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