점프

문제

$22$ 이상의 $NN$에 대해 $11$부터 $NN$까지의 번호가 붙은 $NN$개의 정점이 번호 순서대로 일직선상에 놓여있고, 각 $ii$ (1 ≤ i ≤ N − 1)에 대해 정점 $ii$와 $i+1i\; +\; 1$을 양방향으로 잇는 간선이 있는 상황을 고려하자.

예를 들어, $N=5N\; =\; 5$인 경우에는 아래 그림과 같이 정점과 간선이 배치된다.

정올이는 이 그래프 위에서 점프하여 이동할 수 있다. 정올이가 어느 한 정점에서 다른 정점으로 점프하면, 그 사이에 있는 모든 간선을 한 번씩 지나간다.

예를 들어:

• 정올이가 정점 $44$에서 $22$로 점프했다면, 정올이는 정점 $33$과 $44$ 사이의 간선과 정점 $22$와 $33$ 사이의 간선을 각각 한 번씩 지나간다.
• 정올이가 정점 $33$에서 $44$로 점프했다면 정점 $33$과 $44$ 사이의 간선을 한 번 지나간다.

정올이는 정점 $11$에서 시작해 N − 1번의 점프를 거쳐 정점 $NN$에 도착했고, 그 과정에서 모든 정점을 정확히 한 번씩 방문했다. (처음에 정점 $11$에 있었던 것도 방문으로 간주한다.)

다시 말해, 정올이가 정점들을 방문한 순서를 p_1 → p_2 → \cdots → p_{N-1} → p_N 이라고 할 때, $p_1=1p\_1\; =\; 1$이고, $p_N=Np\_N\; =\; N$ 이며, $\{p_1,p_2,\cdots ,p_N\}=\{1,2,\cdots ,N\}\backslash \{p\_1\; ,\; p\_2\; ,\backslash cdots\; ,\; p\_N\; \backslash \}\; =\; \backslash \{1,\; 2,\; \backslash cdots\; ,\; N\backslash \}$이다.

이때, 정올이가 점프하는 과정에서 각 $ii$ (1 ≤ i ≤ N − 1)에 대해 정점 $ii$와 $i+1i\; +\; 1$ 사이 간선을 지나간 횟수를 $c_{i}c\_i$라고 하자.

예를 들어, 정올이가 (p_1 = 1) → (p_2 = 3) → (p_3 = 4) → (p_4 = 2) → (p_5 = 5) 순서로 방문했다면, $c_1=1,c_2=3,c_3=3,c_4=1c\_1\; =\; 1,\; c\_2\; =\; 3,\; c\_3\; =\; 3,\; c\_4\; =\; 1$이 된다.

정올이가 정점들을 방문하면서 각 간선을 지난 횟수를 나타내는 수열 $c=(c_1,c_2,\cdots ,c_N-1)c\; =\; (c\_1\; ,\; c\_2\; ,\backslash cdots\; ,\; c\_N-1)$이 주어졌을 때, 이로부터 정올이의 방문 순서 $p_1,p_2,\cdots ,p_{N}p\_1\; ,\; p\_2\; ,\backslash cdots\; ,\; p\_N$을 구하는 프로그램을 작성하라.

주어지는 수열 $cc$는 항상 어떤 방문 순서에 의해 만들어진 것이므로, 이를 만족하는 방문 순서는 항상 존재한다. 만약 가능한 방문 순서가 여러 가지라면 아무것이나 하나 구하면 된다.

입력

첫 번째 줄에 정점의 개수 $NN$이 주어진다.

두 번째 줄에 N − 1개의 정수 $c_1,c_2,\cdots ,c_{N-1}c\_1\; ,\; c\_2\; ,\backslash cdots\; ,\; c\_\{N-1\}$이 공백을 사이에 두고 주어진다. 이때, $c_{i}c\_i$는 정점 $ii$와 $i+1i\; +\; 1$ 사이의 간선을 지나간 횟수를 의미한다.

출력

정올이의 가능한 방문 순서 $p_1,p_2,\cdots ,p_{N}p\_1\; ,\; p\_2\; ,\backslash cdots\; ,\; p\_N$을 공백으로 구분하여 출력한다. 만약 가능한 방문 순서가 여러 가지라면 아무것이나 하나 출력한다.

5
1 3 3 1

1 3 4 2 5

7
1 3 3 5 3 1

1 6 2 3 5 4 7