🧩 N-Queen (Hard)

N-Queen 문제는 크기가 $N \times N$인 체스판 위에 퀸 $N$개를 서로 공격할 수 없게 놓는 문제이다.

$N$이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.

이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 30)$

두 번째 줄에 정수 $Q\_1$, $Q\_2$, $Q\_3$, $\cdots$, $Q\_N$이 주어진다. $Q\_i$는 $i$번째 행에 있는 퀸의 열의 번호를 의미한다. $(0 \le Q\_i \le N)$

만약 $Q\_i$가 0이라면 $i$번째 행에는 퀸이 놓여있지 않다는 뜻이다.

퀸이 서로 공격하는 올바르지 않은 상태의 입력 혹은 $N$개의 퀸이 모두 놓여있는 경우의 입력은 없다.

첫 번째 줄에 정수 $A\_1$, $A\_2$, $A\_3$, $\cdots$, $A\_N$를 출력한다. $A\_i$는 $i$번째 행에 있는 퀸의 열의 번호를 의미한다. $(1 \le A\_i \le N)$

만약 $N$개의 퀸을 놓을 수 없다면 -1을 출력한다.