스파이더맨은 건물 사이를 오르락 내리락 하면서 이동한다. 중요한 것은 땅으로 시작해서 마지막은 땅으로 끝나야 한다.

물론 , 그는 땅 아래로는 내려갈 수는 없다!!! 또한 , 가능한 올라간 높이를 최소로 하고 싶다.( 스파이더맨은 인정하려 들지않겠지만 , 그는 고소공포증이 있다)

그는 올라가야할지 내려가야 할지 결정하는데 당신의 도움이 필요하다.

답은 합리적이어야 한다. 즉 시작은 0 미터에서 시작하고 0 미터 아래로는 내려가지 못하고 지상까지 내려오는데 최소의 높이를 찾아야 하고 , 입력받은 순서를 임의로 조정해서는 안된다.

건물 수 4 이고 20 20 20 20 인 경우

1. down up down up 지하로는 내려 가지 못해 ( X )
2. up up down down 최대 높이 40
3. up down up down 최대 높이 20

다른 예로 , 3 2 5 3 1 2 이면 up, up, down, up, down, down 이 최선의 방법이다. 3 4 2 1 6 4 5 이면 답이 없다.

요약하면 , 고소 공포증을 가진 스파이더 맨이 높이 0 부터 시작하여 up , down 과정을 반복하여 높이 0 즉 지상으로 내려오는 데 높이를 최소로 하는 패스를 출력하는 문제이다.

입력

• 첫 번째 수는 높이의 수 M ( M <= 40 ) 이고 ,
• 다음 줄에는 M 개의 양의 정수가 주어진다. 모든 건물의 총 높이는 1000 을 넘지 않는다.

출력

입출력 예

입력

4
20 20 20 20 

출력

UDUD 

입력

6 
3 2 5 3 1 2 

출력

UUDUDD 

입력

7 
3 4 2 1 6 4 5

출력

IMPOSSIBLE

출처: Svenskt Masterskap i Programmering/Norgesmesterskapet 2003