기차 교차로 |
---|
무지개 마을과 달님 마을을 연결하는 기찻길이 있다. 이 기찻길은 외길이기 때문에 서로 물건을 주고 받기가 불편했다. 이 불편을 해소하기 위해서 두 마을의 중간에 T자 모양의 교차로를 설치했다. 이 교차로를 설치한 후에는 두 마을에서 동시에 기차가 출발하더라도 중간에서 교차할 수 있게 되어 더욱 편리해졌다. 게다가 무지개 마을에서 느린 화물 열차를 보낸 후에 연달아 빠른 특급 열차를 보내도 중간의 교차로에서 앞지를 수 있게 되었다.
교차로에서의 작업은 다음 두 가지가 있을 수 있다. S작업 : 무지개 마을에서 오는 기차를 교차로에 넣는다. 예를 들어, 무지개 마을에서 느린 화물 열차인 1번 기차를 보낸 뒤 빠른 특급 열차인 2번 기차를 보내었다면 다음과 같은 작업으로 그 순서를 바꾸어 줄 수 있다. ① S작업 : 1번 기차를 교차로에 넣는다. 1, 2, ... , N의 번호를 가진 N대의 기차가 있다고 가정하자. 이 기차들이 무지개 마을에서 어떤 순서대로 출발하더라도 달님 마을에 번호 순서대로 도착하게 하려 한다. 만일 가능하다면 교차로에서 어떠한 작업을 거쳐야 하는지 그 작업을 차례대로 출력하는 프로그램을 작성하시오. |
입력 | |
---|---|
첫째 줄에는 기차의 수 N이 주어지며, 두 번째 줄에는 무지개 마을에서 출발하는 기차들의 번호를 나타내는 1이상 N이하의 서로 다른 N개의 정수들이 먼저 출발한 순서대로 주어진다. N이 1 이상 100 이하의 정수이다. |
출력 | |
---|---|
달님 마을에 번호 순서대로 기차가 도착할 수 있는 경우 교차로에서 이루어진 작업 순서를 차례대로 한 줄에 이어 출력한다. 번호 순서대로 도착하는 것이 불가능할 경우에는 IMPOSSIBLE 라고 출력한다. (대소문자를 다르게 출력하는 경우 오답처리된다.) |
예시 | |||
---|---|---|---|
1 | 입력 | 4 4 3 2 1 | |
출력 | SSSSXXXX |