题目背景

A geometrical marvel adds an element of mathematical elegance...

while True:
  print('%%%')

题目描述

给定一个长度为 $n$ 的序列 $a$。显然有 $2^n$ 个子序列，对于每个子序列求和，求出所有和中第2大的和。（本题中空序列也算子序列，空序列内所有元素之和为 $0$）

例如对于 $n=3,a=[3,-4,2]$，所有子序列为 $[3,-4,2],[3,-4],[3,2],[-4,2],[3],[-4],[2],[]$，对应的和分别为 $1,-1,5,-2,3,-4,2,0$，显然所有和中第2大的和为 $3$。

输入格式

第一行一个正整数 $n$。

第二行一个长度为 $n$ 的序列 $a$，元素之间以空格隔开，元素均为整数。

输出格式

一个整数，表示对于序列 $a$ 的每个子序列求和，所有和中第2大的和。

样例 #1

样例输入 #1

3
3 -4 2

样例输出 #1

3

提示

对于 $20\%$ 的测试点，$1 \le n \le 10$。

对于 $40\%$ 的测试点，$1 \le n \le 20$。

对于另外 $10\%$ 的测试点，$1 \le a_i \le 10^9$。

对于 $100\%$ 的测试点，$1 \le n \le 2\times 10^5,-10^9 \le a_i \le 10^9$。

时限500ms。