10002 - Sing Me to Sleep

通过次数

43

提交次数

360

时间限制 : 1 秒
内存限制 : 512 MB

Wait a second, let me catch my breath
Remind me how it feels to hear your voice
Your lips are movin', I can't hear a thing
Livin' life as if we had a choice

Anywhere, any time
I would do anything for you
Anything for you
Yesterday got away
Melody stuck inside your head
A song in every breath

——Alan Walker 《Sing Me to Sleep》

15824416647101.png

wlxsq正在做一个美梦,梦里有n个画面,其中第i个画面有一个甜蜜值a_i

他希望能选取其中n-1个画面,使得他们的甜蜜值乘积最大。

他现在想问问你,选取的这n-1个画面的甜蜜值在乘积最大的情况下,他们的和最大是多少?

输入

第一行,输入n

接下来,输入n个数,表示a_i

输出

输出在甜蜜值乘积最大的情况下,他们和的最大值。

样例

输入

5
2 3 3 3 3

输出

12

输入

3
0 0 4

输出

4

提示

样例解释

第一组样例,选取{3,3,3,3}这四个画面时乘积为81,乘积最大。此时的和为3+3+3+3=12

第二组样例,选取{0,4}或者{0,0}画面乘积均为0,乘积最大。但要求最大乘积相同时和最大,故选取{0,4}。此时的和为0+4=4

数据范围

对于20%的数据,2\le n\le 10, -5\le a[i]\le 5

对于30%的数据,2\le n\le 55, 0\le a[i]\le 100

对于50%的数据,2\le n\le 55, a[i]不为0

对于100%的数据,2\le n\le 55, -100\le a[i]\le 100