삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다. 이 알고리즘은 뒤섞여 있는 카드를 순서대로 정리하는 방법과 같이, 카드를 한 장씩 뽑아 값에 따라 적절한 곳에 끼워 넣는 것을 반복하여 정리한는 것 처럼, 데이터 집합에서 요소를 하나식 뽑아 적절한 곳에 끼워 넣는 것을 반복하여 데이터 집합을 정렬하는 방법입니다.

입력데이터 

 6

 6 4 2 3 1 5

1단계 : 4 6 2 3 1 5     -> 4를 1번째 자리에 삽입

2단계 : 2 4 6 3 1 5     -> 2를 1번째 자리에 삽입

3단계 : 2 3 4 6 1 5     -> 3을  2번째 자리에 삽입

4단계 : 1 2 3 4 6 5     -> 1을 1번째 자리에 삽입

5단계 : 1 2 3 4 5 6     -> 5를 5번째 자리에 삽입

위와 같이 정렬 과정을 거칠때, 정렬의 각 단계에서 정렬이 필요한 요소가 삽입될 자리를 출력하는 프로그램을 작성하시오.

첫 줄에는 정렬하고자 하는 데이터의 갯수 n이 입력된다.( 2 <= n <= 100)

둘째 줄에는 n개의 데이터가 공백을 기준으로 입력된다.

 정렬되는 각 단계별 데이터가 삽입되는 위치를 출력한다.

위키백과 삽입정렬 : ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC