魔力屏障

题目描述

小 $Z$ 生活在神奇的魔法大陆上。今天他的魔法老师给了它这样一个法阵作为它的期末考试题目：

法阵由从左至右 $n$ 道魔力屏障组成，每道屏障有一个临界值 $a$ ，如果它承受攻击的魔力值 $\ge a$ ，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力值为两次攻击魔力值之和，新的攻击会继续向右移动。小 $Z$ 可以在法阵中任意一个位置释放任意大小魔力值的攻击，攻击会向右移动直到遇到一个还未被摧毁的屏障或离开法阵。

对于所有 $1 \le i \le n$ ，小 $Z$ 希望用最小的法力值使得第 $1$ ∼ $i$ 道屏障全部破碎。

输入格式

第一行一个正整数 $n$ 表示屏障的数量。

第二行 $n$ 个正整数，第 $i$ 个数为第 $i$ 道屏障的临界值。

输出格式

一行 $n$ 个数，第 $i$ 个表示使第 $1$ ∼ $i$ 道屏障全部破碎的最小法力值。两个数之间用一个空格隔开。

样例输入1

5
10 3 3 8 4

样例输出1

10 10 11 17 17

【样例 2】

见选手目录下的 magic2*.in* 与 magic2*.ans*。

该样例与子任务 2 满足同样的约束条件。

【样例 3】

见选手目录下的 magic3*.in* 与 magic3*.ans*。

该样例与子任务 3 满足同样的约束条件。

【样例 4】

见选手目录下的 magic4*.in* 与 magic4*.ans*。

该样例与子任务 4 满足同样的约束条件。

数据规模和约定

本题开启子任务测试。对于所有数据满足 $1 \le n \le 70, 1 \le a_i \le 150$ 。