时间限制： 1.0 秒

空间限制： 256 MB

问题描述

在一条街上有 $n$ 个卖菜的商店，按 $1\sim n$ 的顺序排成一排，这些商店都卖一种蔬菜。

第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。

注意，编号为 $1$ 的商店只有一个相邻的商店 $2$，编号为 $n$ 的商店只有一个相邻的商店 $n-1$，其他编号为 $i$ 的商店有两个相邻的商店 $i-1$ 和 $i+1$。

给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。

字典序大小的定义：对于两个不同的价格序列 $(a_1, a_2, \dots, a_n)$ 和 $(b_1, b_2, b_3, \dots, b_n)$，若存在 $i\ (i\ge 1)$, 使得 $a_i<b_i$，且对于所有 $j<i，a_j=b_j$，则认为第一个序列的字典序小于第二个序列。

输入格式

从标准输入读入数据。

输入的第一行包含一个整数 $n$，表示商店的数量。

第二行包含 $n$ 个正整数，依次表示每个商店第二天的菜价。

输出格式

输出一行，包含 $n$ 个正整数，依次表示每个商店第一天的菜价。

8
2 2 1 3 4 9 10 13

2 2 2 1 6 5 16 10

数据规模和约定

对于 $30\%$ 的评测用例，$2\le n\le5$，第二天每个商店的菜价为不超过 $10$ 的正整数；

对于 $60\%$ 的评测用例，$2\le n\le 20$，第二天每个商店的菜价为不超过 $100$ 的正整数；

对于所有评测用例，$2\le n\le 300$，第二天每个商店的菜价为不超过 $100$ 的正整数，保证数据一定是有解的。

请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。