주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것 뿐이다.

즉, 한 번에 다른 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다.

4 1 5 3 2 의 경우 다음과 같이 정렬 할 수 있다.

4 1 5 3 2 -> 3 2 4 1 5 -> 3 4 1 2 5 -> 1 2 3 4 5

이와 같이 입력으로 1에서 N까지의 서로 다른 N개의 정수들로 구성된 숫자 열이 주어질 때 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.

정렬2 timer 1s memory - MB

정렬2 1s - MB