思路：前后缀分解

对于位置$i$而言，$f(i)$由以下三个部分组成

• 左边的最大值left_max
• 右边的最大值right_max
• $2a[i]$

因此我们可以预处理出后缀和数组$r[i]$表示位置$i$右边的最大值

左边的最大值我们可以一边遍历一边处理，然后取上述三个部分的max即可

n=int(input())
w=list(map(int,input().split()))
r=[0]*(n+1)
for i in range(n-1,0,-1):
    r[i]=max(r[i+1],w[i])
lft=0
for i in range(n):
    print(max(lft,w[i]*2,r[i+1]),end=' ')
    lft=max(lft,w[i])

题目描述

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

输入描述

第一行输入一个正整数$n$,代表数组大小

第二行输入$n$个正整数$a_i$，代表小红拿到的数组

$1\le n\le 2\times 10^5$

$1\le a_i\le 10^9$

输出描述

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

样例

输入

5
1 3 2 5 4

输出

5 6 5 10 8