D - Seating Order at the Round Table Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

円卓に N 個の席があり、時計回りに席 1, 2, \ldots, N と番号が付いています。

各席 i にスコア P_i を割り当てます。ここで、P_1, P_2, \ldots, P_N は 1 から N までの整数をちょうど 1 回ずつ使った順列でなければなりません。

各席 i の隣の席は次の 2 つです。

  • 席 i - 1（ただし i = 1 のときは席 N）
  • 席 i + 1（ただし i = N のときは席 1）

すべての席 i（1 \leq i \leq N）について、隣の 2 席のうちスコアが P_i より小さい席の個数がちょうど A_i となるようにしたいです。

条件を満たす順列 P を 1 つ求めてください。条件を満たす順列が複数存在する場合は、そのいずれを出力しても正解とします。存在しない場合は -1 を出力してください。

制約

  • 3 \leq N \leq 5 \times 10^5
  • 0 \leq A_i \leq 2
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、席の個数を表す整数 N が与えられる。
  • 2 行目には、各席 i について隣の 2 席のうちスコアが自分より小さい席の個数の目標値を表す整数 A_i が、スペース区切りで N 個与えられる。

出力

条件を満たす順列 P が存在する場合、以下の形式で出力せよ。

P_1 P_2 \ldots P_N

条件を満たす順列 P が存在しない場合、-1 を出力せよ。

入力例 1

5
0 1 2 0 2

出力例 1

1 3 5 2 4

入力例 2

3
1 1 1

出力例 2

-1

入力例 3

12
0 1 2 1 1 0 1 2 0 1 2 1

出力例 3

1 4 12 9 6 2 7 10 3 8 11 5

入力例 4

30
0 1 1 2 1 1 0 1 1 2 1 1 1 0 1 1 2 1 1 0 1 1 1 2 1 1 0 1 1 2

出力例 4

1 6 15 24 16 7 2 8 17 29 25 18 9 3 10 19 26 20 11 4 12 21 27 30 22 13 5 14 23 28

入力例 5

3
0 2 1

出力例 5

1 3 2

Score : 400 pts

Problem Statement

There are N seats at a round table, numbered 1, 2, \ldots, N in clockwise order.

We assign a score P_i to each seat i. Here, P_1, P_2, \ldots, P_N must be a permutation using each integer from 1 to N exactly once.

The neighboring seats of each seat i are the following two:

  • Seat i - 1 (or seat N when i = 1)
  • Seat i + 1 (or seat 1 when i = N)

For every seat i (1 \leq i \leq N), we want the number of neighboring seats whose score is smaller than P_i to be exactly A_i.

Find one permutation P that satisfies the conditions. If there are multiple permutations satisfying the conditions, any of them will be accepted. If none exists, output -1.

Constraints

  • 3 \leq N \leq 5 \times 10^5
  • 0 \leq A_i \leq 2
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of seats.
  • The second line contains N integers A_i separated by spaces, where each A_i represents the target number of neighboring seats with a score smaller than that of seat i.

Output

If a permutation P satisfying the conditions exists, output it in the following format:

P_1 P_2 \ldots P_N

If no permutation P satisfying the conditions exists, output -1.

Sample Input 1

5
0 1 2 0 2

Sample Output 1

1 3 5 2 4

Sample Input 2

3
1 1 1

Sample Output 2

-1

Sample Input 3

12
0 1 2 1 1 0 1 2 0 1 2 1

Sample Output 3

1 4 12 9 6 2 7 10 3 8 11 5

Sample Input 4

30
0 1 1 2 1 1 0 1 1 2 1 1 1 0 1 1 2 1 1 0 1 1 1 2 1 1 0 1 1 2

Sample Output 4

1 6 15 24 16 7 2 8 17 29 25 18 9 3 10 19 26 20 11 4 12 21 27 30 22 13 5 14 23 28

Sample Input 5

3
0 2 1

Sample Output 5

1 3 2