题目描述
Farmer John 的奶牛要为一道名叫 Haybales 的竞赛题构造数据。设有一个非降的整数数组 x1≤x2≤⋯≤xN 和一个整数 K。对每个下标 i,定义 ji 为使 xji≤xi+K 成立的最大下标。
给定 j1,…,jN,构造任意一组数组和 K,使它们符合上述关系。要求 0≤xi≤1018、1≤K≤1018。保证 i≤ji、j1≤j2≤⋯≤jN≤N,并且至少有一组解。
输入格式
第一行一个整数 N(1≤N≤105)。第二行 N 个整数 j1,…,jN。
输出格式
第一行输出 K,随后各用一行依次输出 x1,…,xN。当 ji=N 时,只需满足 xN≤xi+K,没有下一个元素。若有多组可行解,任意输出一组。
样例 #1
样例输入 #1
6
2 2 4 5 6 6
样例输出 #1
6
1
6
17
22
27
32
样例解释 #1
样例取 K=6,数组为 [1,6,17,22,27,32]。
| i |
xi+K |
不大于该值的最后一个元素 |
下一个元素 |
ji |
| 1 |
7 |
6 |
17 |
2 |
| 2 |
12 |
| 3 |
23 |
22 |
27 |
4 |
| 4 |
28 |
27 |
32 |
5 |
| 5 |
33 |
32 |
无 |
6 |
| 6 |
38 |
另一种合法输出是取 K=1,数组为 [1,2,4,5,6,7]。
测试点性质
50% 的输入满足 N≤5000,其余输入无额外限制。