Challenge: Insertion Sort Steps

Lab C++ Beginner 10 points

Sort n numbers with insertion sort. After inserting each item (from the second on), print the vector.

Input

Line 1: n (n ≥ 2). Line 2: n whole numbers.

Output

n − 1 lines.

Example

Input

4
7 3 5 1

Output

3 7 5 1
3 5 7 1
1 3 5 7

Sample input available Sample output available

Editor

C++

Hints

Take v[i] as the card.

Shift bigger items right, then drop the card in the gap.

Solution explanation

After step i, the first i + 1 items are sorted.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    for (int i = 1; i < n; i++) {
        int card = v[i], j = i - 1;
        while (j >= 0 && v[j] > card) { v[j + 1] = v[j]; j--; }
        v[j + 1] = card;
        for (int k = 0; k < n; k++) cout << v[k] << (k + 1 < n ? " " : "\n");
    }
    return 0;
}

Output

Answer