U377820 选礼物

由于小未已经刷了 $20$ 道题了， ~~等待他的是更难 AC 的题，~~ 所以他可以获得一些礼物。

共有 $n$ 份礼物摆在小未面前，如果小未获得了第 $i$ 份礼物，他的开心值就会增加 $a_i$（如果 $a_i < 0$，那么他的开心值就会减少 $|a_i|$）。 小未必须选择把第 $L$ 份礼物到第 $R$ 份礼物都拿走（$1 \le L \le R \le n$），并且他只有一次选择的机会。 小未如何选择礼物才能使自己获得的开心值最大呢？请你输出小未能获得的最大开心值。

输入共 $n + 1$ 行： 第一行输入一个正整数，表示 $n$； 接下来的 $n$ 行，每行输入一个整数，第 $i + 1$ 行的整数表示 $a_i$。

输出一个整数，表示小未能获得的最大开心值。

本题共有十二组测试数据： * 对于前六组测试数据，满足 $1 \le n \le 10, |a_i| \le 10^6$； * 对于前十组测试数据，满足 $1 \le n \le 10^3, |a_i| \le 10^6$； * 对于所有的测试数据，满足 $1 \le n \le 10^5, |a_i| \le 10^6$。 通过前十组测试数据即可获得 $100$ 分。