养蛊神器

题目信息

时间限制: 1s

空间限制: 256M

输入文件: bug.in

输出文件: bug.out

题目描述

A 君在机缘巧合下得到了一把养蛊神器，于是 A 君希望培养出迄今为止战斗力最强的 Bug。A 君把现有的 $n$ 个 Bug 排成一个序列 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 个 Bug 的战斗力。A 君需要重复进行以下操作直到只剩下一个 Bug：

• 选择一个端点（指最左边或者最右边）的 Bug，删除它。
• 选择一个非端点的 Bug，将它的战斗力变为当前它左右两个相邻 Bug 的战斗力之和，然后删除左右两边的 Bug。

求操作结束后剩下的一个 Bug 的最高战斗力是多少，并求出需要的最少操作数。

输入格式

第一行一个整数，表示 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

第一行一个整数，表示操作结束后剩下的 Bug 的最高战斗力。

第二行一个整数，表示需要的最少操作数。

样例

样例输入1

6
-1 5 2 -2 3 -3

样例输出1

5
4

样例输入2

4
-2 -4 -1 -3

样例输出2

-1
3

样例输入3

10
32644 -36604 -178874 -98683 92567 -272835 -35544 -151678 -8486 -197803

样例输出3

125211
5

数据范围与提示

• 对于前 $10 \%$ 的数据，满足 $n \leq 10$ 。
• 对于前 $20 \%$ 的数据，满足 $n \leq 2000$ 。
• 对于 $100 \%$ 的数据，满足 $1 \leq n \leq 10^6,\left|a_i\right| \leq 10^{10}$ 。