전선 연결하기 Batch
| Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
|---|---|---|---|---|---|
| 1000 ms | 64 MiB | 85 | 18 | 5 | 27.78% |
석환이는 "Lightballb"라는 상품을 판매합니다. Lightballb 한 세트에는 두 개의 같은 자연수 번호가 적혀 있는 공이 들어있습니다. 이 공은 평상시에는 공의 역할을 하다가, 같은 번호가 쓰여 있는 두 공을 전선으로 연결하면 전구의 역할을 한다고 합니다.
승현이는 석환이의 상품이 전혀 팔리지 않는다는 소식을 듣고, 석환이를 돕기 위해 $n$개의 Lightballb 세트를 구매했습니다. 따라서 승현이는 $2n$개의 공을 가지고 있으며, 1 이상 $n$ 이하의 모든 자연수 $k$에 대해 $k$가 적혀 있는 공은 정확히 2개입니다.
승현이는 방대한 공들을 보관할만한 장소를 찾다가, 아래와 같이 생긴 길쭉한 보관함을 찾고 그 안에 공을 무작위로 넣었습니다.
다음 날, 승현이는 공을 사용하기 위해 보관함에서 공을 꺼내려고 시도했지만, 공들은 꼼짝도 하지 않았습니다! 공이 반짝반짝 빛나는 모습을 보고 싶던 승현이는 절망감에 빠졌습니다. 낙담하고 있던 그 때, 승현이는 전선이 보관함을 뚫고 들어간다는 사실을 알아냈습니다! 승현이는 공들에 전선을 잘 꽂아 모든 공들이 빛나는 모습을 보고자 합니다.
무턱대고 전선을 끼우면 고장이 날 우려가 있기 때문에, 승현이는 미리 전선을 어떻게 연결할지에 대한 계획을 수립하려고 합니다. 우선, 승현이는 보관함과 전선이 움직이는 것을 방지하기 위해, 이들을 반드시 바닥 위에 놓기로 했습니다. 하지만, 이것만으로는 위험에 대비할 수 없다고 생각한 승현이는 다음과 같은 규칙을 세웁니다.
- 합선의 우려가 있으므로, 전선끼리 서로 교차하면 안 된다.
- 한 전선의 모든 부분은 보관함의 위에 있거나 보관함의 아래에 있어야 한다.
승현이는 위 규칙을 만족하면서 전선을 연결하여 모든 공이 빛나도록 할 수 있는 방법이 존재하는지 알고자 합니다. 하지만 전구의 개수가 너무 많아 스스로 해결할 수 없었고, 여러분에게 도움을 요청했습니다. 승현이의 보관함에 적혀 있는 공의 번호가 차례대로 주어질 때, 각 공의 전선이 보관함 위에 있어야 하는지, 아래에 있어야 하는지를 결정하는 프로그램을 작성하세요.
입력 형식
첫 번째 줄에 자연수 $n$이 주어집니다.
두 번째 줄에 $a_{1}, a_{2}, ..., a_{2n - 1}, a_{2n}$이 공백을 사이로 두고 차례대로 주어집니다. 여기서 $a_{i}$는 승현이의 보관함에서 왼쪽에서부터 $i$번째에 위치한 공에 적혀 있는 번호를 나타냅니다.
출력 형식
만약 주어진 조건을 만족하면서 모든 공을 빛나게 하는 방법이 존재하지 않는다면, "IMPOSSIBLE" (따옴표 제외)를 출력합니다.
만약 방법이 존재한다면, 첫 번째 줄에 길이가 $2n$인 문자열을 출력합니다. 이 중 $i$ ($1 \le i \le 2n$)번째 글자는, 왼쪽에서 $i$번째에 위치한 공에 꽂는 전선이 보관함 위에 있어야 한다면 '^', 보관함 아래에 있어야 한다면 'v'이어야 합니다.
제약 조건
- $1 \le n \le 300, 000$
- 모든 $i$ ($1 \le i \le 2n$)에 대해, $1 \le a_{i} \le n$
- 모든 $k$ ($1 \le k \le n$)에 대해, $k$는 수열 $a$에서 정확히 2번 나타납니다.
부분문제
| 부분문제 | 점수 | n |
|---|---|---|
| 1 | 9 | ≤ 10 |
| 2 | 15 | ≤ 1,000 |
| 3 | 37 | ≤ 100,000 |
| 4 | 39 | ≤ 300,000 |
예제
예제 1
입력
4
1 2 3 2 3 1 4 4
출력
^^v^v^vv
예제 2
입력
3
1 2 3 3 2 1
출력
^^^^^^
예제 3
입력
3
1 2 3 1 2 3
출력
IMPOSSIBLE
참고로, 맨 위의 예제는 그림 (A)와 같습니다.