序列恢复 (ssr)

本题使用文件输入输出，请在程序开头加入：

freopen("ssr.in", "r", stdin);
freopen("ssr.out", "w", stdout);

题目描述

Y 同学最近在研究一种特殊的信号处理设备。该设备记录了一组长度为 $N$ 的离散信号序列 $S = \{c_1, c_2, \dots, c_n\}$。为了分析信号的自相关性，Y 同学计算了该序列的 自匹配强度序列 $P$（在算法竞赛中通常被称为 $Z$ 函数）。

对于长度为 $N$ 的序列 $S$，其自匹配强度序列 $P$ 的第 $i$ 个元素 $P_i$ 定义为：满足 $S[1 \dots x] = S[i \dots i+x-1]$ 的最大非负整数 $x$。根据定义，$P_1$ 始终等于 $N$。

然而，Y 同学在完成计算后发现，记录的原始信号序列 $S$ 的第一个信号 $c_1$ 实际上是由于传感器预热产生的随机噪声，并非有效数据。为了获得准确的分析结果，他需要求出剔除噪声后的有效信号序列 $T = \{c_2, c_3, \dots, c_n\}$ 的自匹配强度序列 $Q$。

不幸的是，由于存储空间限制，原始信号序列 $S$ 在计算完 $P$ 后已被销毁，目前仅保留了长度为 $N$ 的序列 $P$。请你根据已知的 $P$ 序列，推导出序列 $T$ 的自匹配强度序列 $Q$。

由于原始信号序列 $S$ 可能并不唯一，如果对于 $T$ 的某个位置 $j$，其对应的 $Q_j$ 无法通过已知信息唯一确定，请在该位置输出 $-1$。

输入格式

从 ssr.in 文件读入数据。

第一行包含一个整数 $N$，表示原始信号序列 $S$ 的长度。

第二行包含 $N$ 个整数 $P_1, P_2, \dots, P_n$，表示序列 $S$ 的自匹配强度序列。

输出格式

输出到 ssr.out 文件。

输出一行 $N-1$ 个整数 $Q_1, Q_2, \dots, Q_{n-1}$，表示序列 $T$ 的自匹配强度序列。对于无法唯一确定的位置，输出 $-1$。

样例

样例输入 #1

5
5 4 3 2 1

样例输出 #1

4 3 2 1

样例输入 #2

7
7 2 1 0 2 1 0

样例输出 #2

6 1 0 -1 1 0

样例输入 #3

7
7 0 1 0 3 0 1

样例输出 #3

6 0 0 0 2 0

数据范围与约定

对于 $100\%$ 的数据，保证 $2 \le N \le 10^6$，$0 \le P_i \le N$，且至少存在一个符合条件的字符串。

• 特殊性质 A：保证对于所有 $2 \le i \le N$，有 $P_i \le 1$。
• 特殊性质 B：保证输入的 $P$ 序列中，除 $P_1$ 外所有项均为 $0$。

大样例

点击链接 [bigdata1.in](file://bigdata1.in) 和 [bigdata1.out](file://bigdata1.out) 下载大样例 1 的输入输出数据。

点击链接 [bigdata2.in](file://bigdata2.in) 和 [bigdata2.out](file://bigdata2.out) 下载大样例 2 的输入输出数据。

点击链接 [bigdata3.in](file://bigdata3.in) 和 [bigdata3.out](file://bigdata3.out) 下载大样例 3 的输入输出数据。

点击链接 [bigdata4.in](file://bigdata4.in) 和 [bigdata4.out](file://bigdata4.out) 下载大样例 4 的输入输出数据。