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

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

정올이는 이 그래프 위에서 점프하여 이동할 수 있다. 정올이가 어느 한 정점에서 다른 정점으로 점프하면, 그 사이에 있는 모든 간선을 한 번씩 지나간다.
예를 들어:
- 정올이가 정점 \(4\)에서 \(2\)로 점프했다면, 정올이는 정점 \(3\)과 \(4\) 사이의 간선과 정점 \(2\)와 \(3\) 사이의 간선을 각각 한 번씩 지나간다.
- 정올이가 정점 \(3\)에서 \(4\)로 점프했다면 정점 \(3\)과 \(4\) 사이의 간선을 한 번 지나간다.

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

다시 말해, 정올이가 정점들을 방문한 순서를 \(p_1 → p_2 → \cdots → p_{N-1} → p_N\) 이라고 할 때, \(p_1 = 1\)이고, \(p_N = N\) 이며, \(\{p_1 , p_2 ,\cdots , p_N \} = \{1, 2, \cdots , N\}\)이다.

이때, 정올이가 점프하는 과정에서 각 \(i\) (\(1 ≤ i ≤ N − 1\))에 대해 정점 \(i\)와 \(i + 1\) 사이 간선을 지나간 횟수를 \(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 = 1\)이 된다.

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

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

• 주어지는 모든 수는 정수이다.
• \(2 ≤ N ≤ 200\, 000\)
• \(1 ≤ i ≤ N − 1\)인 모든 \(i\)에 대해
• \(1 ≤ c_i ≤ 10^{18}\)
• 가능한 방문 순서가 존재하는 입력만 주어진다.

첫 번째 줄에 정점의 개수 \(N\)이 주어진다.
두 번째 줄에 \(N − 1\)개의 정수 \(c_1 , c_2 ,\cdots , c_{N-1}\)이 공백을 사이에 두고 주어진다. 이때, \(c_i\)는 정점 \(i\)와 \(i + 1\) 사이의 간선을 지나간 횟수를 의미한다.

정올이의 가능한 방문 순서 \(p_1 , p_2 ,\cdots , p_N\)을 공백으로 구분하여 출력한다. 만약 가능한 방문 순서가 여러 가지라면 아무것이나 하나 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 고등부 1번