#include <iostream>
#include <vector>

using namespace std;

// Funkcja sortująca tablicę za pomocą sortowania przez wstawianie
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // Element do wstawienia
        int j = i - 1;

        // Przesuwamy elementy arr[0..i-1], które są większe od klucza
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // Wstawiamy klucz w odpowiednie miejsce
    }
}

// Funkcja do wypisywania tablicy
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr;
    int n, num;

    cout << "Podaj liczbę elementów w tablicy: ";
    cin >> n;

    cout << "Podaj elementy tablicy: ";
    for (int i = 0; i < n; ++i) {
        cin >> num;
        arr.push_back(num);
    }

    cout << "Tablica przed sortowaniem: ";
    printArray(arr);

    insertionSort(arr); // Wywołanie funkcji sortującej

    cout << "Tablica po sortowaniu: "; // Poprawiony cudzysłów
    printArray(arr);

    return 0;
}