TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

小風拿到了一個正整數序列 $s_1, s_2, \ldots, s_n$,他很興奮地算出對每個正整數 $i$,以第 $i$ 項為結尾的最長迴文子區間的長度為 $c_i$,但是他現在卻丟失了原來的序列,身為小風的好朋友,請你幫幫他找出一組序列滿足條件吧。

Input Format

輸入第一行只有一個正整數 $n$,代表序列的長度。

輸入第二行有 $n$ 個正整數 $c_1,\ c_2, \ldots,\ c_n$,代表以第 $i$ 項為結尾的最長迴文子區間長度。

  • $2 \leq n \leq 2 \times 10^ 5$

Output Format

對於每一組輸入,請輸出一行包含 $n$ 個正整數 $s_1, s_2, \ldots, s_n$ 滿足題目條件,其中 $s_i$ 需滿足 $1 \leq s_i \leq 10^ 9$。輸入保證至少存在一組序列滿足題目條件。

若存在多組滿足條件的序列,請輸出任意一組。

Sample Input 1

3
1 1 2

Sample Output 1

1 2 2

Sample Input 2

5
1 1 3 3 5

Sample Output 2

1 2 1 2 1

Hints

如果一個區間$s_l, s_{l + 1}, \ldots, s_r$ 滿足對所有 $l \leq i \leq r$ 都有 $s_i = s_{l + r - i}$,那麼這個區間就被稱為迴文子區間。

請注意你可以用的不同數字一共有 $10^ 9$ 個。

Problem Source

IOICamp 2020 Day4 pE

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~49 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2
42 1000 262144 65536 2
43 1000 262144 65536 2
44 1000 262144 65536 2
45 1000 262144 65536 2
46 1000 262144 65536 2
47 1000 262144 65536 2
48 1000 262144 65536 2
49 1000 262144 65536 2