메뉴 건너뛰기

문제

00b02 기차 교차로 8  

시간메모리제출 올바른 답 비율
1초64MB
971
280
28.8%


나의 횟수나의 최근 판정시도 성공 비율
188151
80.3%
기차 교차로 

무지개 마을과 달님 마을을 연결하는 기찻길이 있다. 이 기찻길은 외길이기 때문에 서로 물건을 주고 받기가 불편했다. 이 불편을 해소하기 위해서 두 마을의 중간에 T자 모양의 교차로를 설치했다. 이 교차로를 설치한 후에는 두 마을에서 동시에 기차가 출발하더라도 중간에서 교차할 수 있게 되어 더욱 편리해졌다. 게다가 무지개 마을에서 느린 화물 열차를 보낸 후에 연달아 빠른 특급 열차를 보내도 중간의 교차로에서 앞지를 수 있게 되었다.

 

교차로에서의 작업은 다음 두 가지가 있을 수 있다.

S작업 : 무지개 마을에서 오는 기차를 교차로에 넣는다.
X작업 : 교차로에 있는 첫 기차를 달님 마을로 보낸다.

예를 들어, 무지개 마을에서 느린 화물 열차인 1번 기차를 보낸 뒤 빠른 특급 열차인 2번 기차를 보내었다면 다음과 같은 작업으로 그 순서를 바꾸어 줄 수 있다.

① S작업 : 1번 기차를 교차로에 넣는다.
② S작업 : 2번 기차를 교차로에 넣는다.
③ X작업 : 2번 기차를 교차로에서 빼내어 달님 마을로 보낸다.
④ X작업 : 1번 기차를 교차로에서 빼내어 달님 마을로 보낸다.

1, 2, ... , N의 번호를 가진 N대의 기차가 있다고 가정하자. 이 기차들이 무지개 마을에서 어떤 순서대로 출발하더라도 달님 마을에 번호 순서대로 도착하게 하려 한다. 만일 가능하다면 교차로에서 어떠한 작업을 거쳐야 하는지 그 작업을 차례대로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 기차의 수 N이 주어지며, 두 번째 줄에는 무지개 마을에서 출발하는 기차들의 번호를 나타내는 1이상 N이하의 서로 다른 N개의 정수들이 먼저 출발한 순서대로 주어진다. N이 1 이상 100 이하의 정수이다.

출력

달님 마을에 번호 순서대로 기차가 도착할 수 있는 경우 교차로에서 이루어진 작업 순서를 차례대로 한 줄에 이어 출력한다. 번호 순서대로 도착하는 것이 불가능할 경우에는 IMPOSSIBLE 라고 출력한다. (대소문자를 다르게 출력하는 경우 오답처리된다.)

예시
1입력
4
4 3 2 1
출력
SSSSXXXX
위로