#P1468. 2023.08.19-MT-第二题-塔子哥的最大数组

2023.08.19-MT-第二题-塔子哥的最大数组

题目内容

塔子哥有一个长度为 nn 的数组 aa ,默认的求和方式是将 aa 中所有元素加起来。

但是塔子哥有一种技能,可以将求和的其中一次加法转换为乘法操作。

在这种情况下,数组 aa 的最大和为多少。

输入描述

第一行,一个正整数 n(1n105)n(1\leq n\leq 10^5) ,表示数组 aa 的大小

第二行,nn 个正整数 ai(1ai109)a_i(1\leq a_i\leq 10^9)

输出描述

一个整数,表示最大和。

样例

输入

3
1 2 3

输出

7

说明

1+2+3=6,1×2+3=5,1+2×3=71+2+3=6, 1\times 2+3=5, 1+2\times 3=7

所以最大和为 77