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

const int MAX = 1e6;

vector<int> v(MAX, 0);

void insertionSort(void)
{
	for (int i = 1; i < v.size(); i++)
	{
		// i 번째까지는 정렬되어있다고 가정
		int temp = v[i];

		int j;

		for (j = i - 1; j >= 0 && v[j] > temp; j--)
		{
			v[j + 1] = v[j];
		}

		v[j + 1] = temp;
	}
}