Page not loading? Try clicking here.
Placeholder

#2492

[고등부] 2025 KOI 1차대회 대비 모의고사 (2주차)

비둘기
Special judge
Subtask
2s 1024MB

Problems

전깃줄 위에 일렬로 N마리의 비둘기가 앉아 있다. 왼쪽에서부터 1, 2, 3, \dots , N번 비둘기이다. 각 비둘기는 오른쪽 또는 왼쪽을 바라보고 있다.

비둘기는 특정한 규칙에 따라 운다.

  • i번 비둘기가 왼쪽을 바라보고 있다면, 자신보다 왼쪽에 있으면서 오른쪽을 바라보는 비둘기의 수만큼 운다.

  • i번 비둘기가 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있으면서 왼쪽을 바라보는 비둘기의 수만큼 운다.

각 비둘기가 운 횟수가 주어졌을 때, 비둘기의 방향을 복원하라.


Input

첫째 줄에 비둘기의 수를 나타내는 정수N (1 \leq N \leq 10^6)이 주어진다.

둘째 줄에 각 비둘기가 운 횟수 A_1, A_2, \dots , A_N (0 \leq A_i \leq N)이 공백을 사이에 두고 주어진다.


Output

가능한 비둘기의 배치가 존재한다면, 길이 N의 0과 1로 이루어진 배열을 출력한다.

 i번째 수가 0이라면 왼쪽을, 1이라면 오른쪽을 바라보고 있음을 뜻한다.

가능한 배치가 여러 개라면 아무거나 출력한다. 불가능하다면 -1을 출력한다.


Subtask

# Score Condition
#120

N \le 20

#220

N\le 100

#320

N\le 500

#420

N\le 5000

#520

추가 제약 조건 없음


Example #1

5
3 1 1 1 2
1 0 0 1 0

Example #2

3
1 2 2
-1

Example #3

4
1 1 1 3
1 1 1 0

Example #4

1
1
-1

Example #5

20
8 8 2 2 6 6 4 5 5 6 4 7 3 3 9 2 2 11 1 1
-1

Example #6

20
10 1 9 2 2 7 7 4 4 5 5 4 6 3 7 2 2 9 1 10
1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0
You must sign in to write code.