MalnaRISC

이른 아침, 크로아티아 IOI 대표팀이 자그레브 공항에 모이기 시작한다. 암스테르담에서 경유해 싱가포르로 가는 긴 여정이다. Malnar 선생은 자몽 음료의 마지막 한 방울까지 마시고는 팀에게 게이트로 이동하라고 명령한다. 늘 그렇듯이 그는 보안 검색대를 지나고 나서 사라졌고, 탑승 몇 분 전에야 나타났다.

대표팀 선수 1: 어디 계셨어요?! 계속 이러시면 다음 비행기도 놓치실 거예요.

Malnar 선생: 이번엔 내 잘못이 아니다. 보안요원들이 날 통과시켜 주지 않았어. 테러리스트인 줄 알았대.

대표팀 선수 2: 테러리스트요?! 선생님은 파리 한 마리도 못 해치실 텐데요. 무슨 일이 있었어요?

Malnar 선생: 아, 요원들이 MalnaRISC(Reduced Instruction Set Computer)를 발견하고는 내가 직접 프로세서를 만들 수 있다는 걸 믿지 않았어. 정수를 정렬하는 데 얼마나 효율적인지 설명해 줬더니 보내 주더라.

대표팀 선수 3: 저도 안 믿었을 거예요. 사실 아직도 안 믿겨요. 그 프로세서가 뭐가 그렇게 특별한데요?

Malnar 선생: 너희는 우리나라 IOI 대표팀이잖아. 굳이 설명해 줄 필요는 없지. 여기 문서가 있으니 알아서 파악해 봐.

대표팀 선수 4: 저한테 주세요. 올해 COI는 이걸로 어셈블리로 풀게요.

MalnaRISC의 어셈블리 언어에는 명령어가 하나뿐이다.

• CMPSWP $R_i$ $R_j$: $R_i > R_j$이면 레지스터 $R_i$와 $R_j$의 값을 교환한다.

MalnaRISC의 특별한 점은 같은 줄에 적힌 모든 명령어가 1나노초 동안 병렬로 실행된다는 것이다. 당연히 각 레지스터는 한 줄에서 최대 한 번만 인자로 쓰일 수 있다.

레지스터 $R_1, R_2, \dots, R_N$에 정수들이 들어 있다. 이 값들을 비내림차순으로 정렬하는 효율적인 어셈블리 코드를 작성하라.

유일한 줄에 문제 설명의 정수 $N$이 주어진다.

첫째 줄에 프로그램의 실행 시간(나노초)을 나타내는 정수 $t$를 출력한다.

다음 $t$개 줄에 $N$개의 레지스터 값을 정렬하는 어셈블리 코드를 출력한다. 각 줄에는 명령어가 적어도 하나 있어야 하고, 각 레지스터는 한 줄에서 한 번만 등장해야 한다. 각 명령어는 "CMPSWP $R_i$ $R_j$" ($1 \le i, j \le N$) 형식이어야 하며, 한 줄 안의 명령어들은 공백 문자 하나로 구분한다.