相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
注意，编号为1的商店只有一个相邻的商店2，编号为
的商店只有一个相邻的商店
1，其他编号为i的商店有两个相邻的商店i1和i1。
给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。
字典序大小的定义：对于两个不同的价格序列a1a2a
和b1b2b3b
，若存在ii1使得aibi，且对于所有ji，ajbj，则认为第一个序列的字典序小于第二个序列。输入格式
输入的第一行包含一个整数
，表示商店的数量。第二行包含
个正整数，依次表示每个商店第二天的菜价。输出格式输出一行，包含
个正整数，依次表示每个商店第一天的菜价。样例输入
82213491013
样例输出
2221651610
数据规模和约定对于30的评测用例，2
5，第二天每个商店的菜价为不超过10的正整数；对于60的评测用例，2
20，第二天每个商店的菜价为不超过100的正整数；对于所有评测用例，2
300，第二天每个商店的菜价为不超过100的正整数。请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。
710
f5线性递推式
时间限制：10s
内存限制：2560MB
问题描样例输入
述336：204
样例输出
123280208
样例说明
样例输入
810
f211111
样例输出
123581321345589144
样例说明
样例输入
101020532737790634932889335818534101179174977780682695192541779962395295668292157661238325351676
样例输出
119744921651421717601080475163399777291546699108479226406175654344671679459752012489415425349454810
数据规模和约定
910
f1010
fr