void insertionSort(vector<int>& A) {
  for(int i = 0; i< A.size(); ++i) {
    int j = i;
    while( j > 0 && A[j-1] > A[j]) {
      swap(A[j-1], A[j]);
      --j;
    }
  }
}

가장 유명한 정렬 알고리즘 중 하나인 삽입 정렬은 위와 같이 구현할 수 있습니다. 정렬이 이루어진 상태의 배열과 정렬이 시작되기 전 초기 위치의 배열이 왼쪽으로 이동한 회수가 주어졌을 때, 초기(원래) 상태의 배열을 구하는 프로그램을 작성하십시오.

* 배열 내의 숫자들은 1 부터 배열의 크기까지 연속되는 숫자입니다.

입력

첫 줄에 배열의 길이 ( 1 이상 50000 이하 ) 입력

초기 상태 배열의 왼쪽 방향 이동 횟수( 공백으로 구분 )

출력

초기 상태 배열