题目描述

周末的阳光很好。你把抽屉里收藏的明信片、车票和小照片都铺在书桌上，想做一条长长的拼贴带，最后只留下一张作为今天的“主角”。

你将这 $n$ 张小卡片按发现顺序排成一列 $a_1,a_2,\dots,a_n$。其中 $a_i$ 代表第 $i$ 张卡片带给你的「氛围值」（也可能是负数：有些回忆酸酸的）。

你将不断重复以下任意一种操作，直到桌上只剩一张卡片为止：

1. 拿走一端：从最左或最右取走一张卡片，什么也不发生。
2. 借光成团：选择一张不在两端的卡片，把它的氛围值改成它左右两张卡片的氛围值之和，然后把左右两张卡片取走（相当于它吸收了两侧的气氛，那两张就退出舞台）。

当只剩下一张卡片时，这张卡片的氛围值就是今天拼贴的总氛围。 请你求出：

• 能得到的最大总氛围值是多少；
• 在达到这个最大值的前提下，所需的最少操作次数是多少（每执行一次上面的任意一种操作都算 1 次）。

小提示：第一种操作像是“只做取舍”；第二种操作像是“把左右的感觉借给中间那张，再让左右退场”。

输入格式

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数，第 $i$ 个为 $a_i$。

输出格式

• 第一行输出一个整数：能得到的最大总氛围值。
• 第二行输出一个整数：在达到最大值的前提下所需的最少操作次数。

样例

样例输入 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 \le 10$。
• 对于前 $20\%$ 的数据，$n \le 2000$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^6,\ \lvert a_i\rvert \le 10^{10}$。

操作次数指执行上述两种操作的总次数。 端点指当前序列最左或最右的位置。