Robot Heartbeat Graph Permutation

Note: In this problem, all sequence indices start from 1.

You are given an algorithmic competition robot whose heart beats n times per minute. The intensity of the i-th beat is a_i. Here, the sequence a₁, a₂, ..., a_n is a permutation of the integers 1 through n.

For each index i, let A_i denote the sequence obtained by removing the i-th element from a, i.e. A_i = [a₁, a₂, ..., a_i-1, a_i+1, ..., a_n].

For any sequence p with distinct elements, define an undirected graph G(p) with |p| nodes numbered from 1 to |p|. For every pair of integers 1 ≤ i < j ≤ |p|, if for every integer k in the range \([i,j]\) we have \[ p_k \in [\min(p_i,p_j),\max(p_i,p_j)], \] then there is an edge between nodes i and j in G(p).

Let F(p) be the length (in number of edges) of a shortest path from node 1 to node |p| in G(p). Define \[ f(a) = [F(A_1), F(A_2), \dots, F(A_n)]. \]

Given a sequence b = [b₁, b₂, ..., b_n] of length n, your task is to output any permutation a of 1,2,...,n such that f(a) = b. It is guaranteed that a solution exists.

In some subtasks, the robot may also provide additional hints. Let G₀ = G(a) and let path₀ be the set of indices along a corresponding to a shortest path from node 1 to node n in G(a). For each j, let path_j be the set of nodes (with the same numbering as in the original graph) visited on some shortest path in G(A_j). The hints provided in the input may include all of path_j (including path₀), or only path₀, or none at all. All hints given are guaranteed to be consistent with some valid permutation.

The package also includes a file checker.cpp (along with testlib.h) that can be used to verify the legality of your output.

inputFormat

The input is given from standard input and has the following format:

 n
 b1 b2 ... bn
 [additional hints may follow]

Here, n is an integer representing the number of heartbeats. The second line contains n integers which represent the sequence b. Additional hint information might be provided in some subtasks, but for the purpose of this problem you can assume that if hints are provided, they are correct.

outputFormat

Output any permutation a of the integers 1, 2, ..., n (separated by spaces) such that f(a) = b holds.

sample

3
1 1 1

1 2 3