题目描述

薯条哥拿到了一个数组。她定义$f(i)$为:将第$i$个元素翻倍后，数组的最大值。现在薯条哥希望你求出$f(1)$到$f(n)$的值。你能帮帮她吗?

输入描述

第一行输入一个正整数$n(1\le n\le 2\times 10^5)$,代表数组大小

第二行输入$n$个正整数$a_i(1\le a_i\le 10^9)$，代表小红拿到的数组

输出描述

$n$个正整数，用空格隔开，代表$f(1)$到$f(n)$的值

样例

输入

5
1 3 2 5 4

输出

5 6 5 10 8