using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ProgrammingContest.Codeforces.Round33
{
class C
{
static int ReadInt()
{
return int.Parse(Console.ReadLine());
}
static int[] ReadInts(int offset = 0)
{
return Console.ReadLine()
.Split(' ')
.Select(s => int.Parse(s) + offset)
.ToArray();
}
static int solve(int n, int[] seq)
{
// xs[i,j]: j個のsum
int[,] xs = new int[2,n+1];
int[] u = new int[n+1], v = new int[n+1];
int[] idx1 = new int[n + 1], idx2 = new int[n + 1];
// ys[i] - ys[j]: sum [j+1,i]
int[] ys = new int[n+1];
for (int i = 0; i < n; i++) ys[i+1] = ys[i] + seq[i];
for (int i = 0; i < n; i++)
{
xs[0, i + 1] = xs[0, i] - seq[i];
xs[1, i + 1] = xs[1, i] - seq[n - 1 - i];
u[i+1] = Math.Max(xs[0, i + 1], u[i]);
v[i+1] = Math.Max(xs[1, i + 1], v[i]);
idx1[i + 1] = idx1[i];
idx2[i+1] = idx2[i];
if (u[i] < xs[0, i + 1]) idx1[i + 1] = i + 1;
if (v[i] < xs[1, i + 1]) idx2[i + 1] = i + 1;
//Console.WriteLine(idx2[i + 1]);
}
// u[0] + v[n] + [idx1,idx2]
// -(-4) + (3 - -4) + 0
int res = int.MinValue;
for (int i = 0; i <= n; i++)
{
res = Math.Max(res, u[i] + ys[n-idx2[n -i]] - ys[idx1[i]] + v[n-i]);
//Console.WriteLine("{0}({1}) - {2}({3})", ys[n - idx2[n - i]], n - idx2[n-i], ys[idx1[i]], idx1[i]);
//Console.WriteLine("u: {0}, v: {1}", u[i], v[n-i]);
}
return res;
}
public static void Mai()
{
int n = ReadInt();
int[] seq = ReadInts();
Console.WriteLine(solve(n,seq));
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CnVzaW5nIFN5c3RlbS5UZXh0OwoKbmFtZXNwYWNlIFByb2dyYW1taW5nQ29udGVzdC5Db2RlZm9yY2VzLlJvdW5kMzMKewogICAgY2xhc3MgQwogICAgewogICAgICAgIHN0YXRpYyBpbnQgUmVhZEludCgpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gaW50LlBhcnNlKENvbnNvbGUuUmVhZExpbmUoKSk7CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgaW50W10gUmVhZEludHMoaW50IG9mZnNldCA9IDApCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gQ29uc29sZS5SZWFkTGluZSgpCiAgICAgICAgICAgICAgICAgICAgICAgICAgLlNwbGl0KCcgJykKICAgICAgICAgICAgICAgICAgICAgICAgICAuU2VsZWN0KHMgPT4gaW50LlBhcnNlKHMpICsgb2Zmc2V0KQogICAgICAgICAgICAgICAgICAgICAgICAgIC5Ub0FycmF5KCk7CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgaW50IHNvbHZlKGludCBuLCBpbnRbXSBzZXEpCiAgICAgICAgewogICAgICAgICAgICAvLyB4c1tpLGpdOiBq5YCL44Guc3VtCiAgICAgICAgICAgIGludFssXSB4cyA9IG5ldyBpbnRbMixuKzFdOwoKICAgICAgICAgICAgaW50W10gdSA9IG5ldyBpbnRbbisxXSwgdiA9IG5ldyBpbnRbbisxXTsKICAgICAgICAgICAgaW50W10gaWR4MSA9IG5ldyBpbnRbbiArIDFdLCBpZHgyID0gbmV3IGludFtuICsgMV07CiAgICAgICAgICAgIC8vIHlzW2ldIC0geXNbal06IHN1bSBbaisxLGldCiAgICAgICAgICAgIGludFtdIHlzID0gbmV3IGludFtuKzFdOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgeXNbaSsxXSA9IHlzW2ldICsgc2VxW2ldOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgeHNbMCwgaSArIDFdID0geHNbMCwgaV0gLSBzZXFbaV07CiAgICAgICAgICAgICAgICB4c1sxLCBpICsgMV0gPSB4c1sxLCBpXSAtIHNlcVtuIC0gMSAtIGldOwogICAgICAgICAgICAgICAgdVtpKzFdID0gTWF0aC5NYXgoeHNbMCwgaSArIDFdLCB1W2ldKTsKICAgICAgICAgICAgICAgIHZbaSsxXSA9IE1hdGguTWF4KHhzWzEsIGkgKyAxXSwgdltpXSk7CiAgICAgICAgICAgICAgICBpZHgxW2kgKyAxXSA9IGlkeDFbaV07CiAgICAgICAgICAgICAgICBpZHgyW2krMV0gPSBpZHgyW2ldOwoKICAgICAgICAgICAgICAgIGlmICh1W2ldIDwgeHNbMCwgaSArIDFdKSBpZHgxW2kgKyAxXSA9IGkgKyAxOwogICAgICAgICAgICAgICAgaWYgKHZbaV0gPCB4c1sxLCBpICsgMV0pIGlkeDJbaSArIDFdID0gaSArIDE7CiAgICAgICAgICAgICAgICAvL0NvbnNvbGUuV3JpdGVMaW5lKGlkeDJbaSArIDFdKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgLy8gdVswXSArIHZbbl0gKyBbaWR4MSxpZHgyXQogICAgICAgICAgICAvLyAtKC00KSArICgzIC0gLTQpICsgMAogICAgICAgICAgICBpbnQgcmVzID0gaW50Lk1pblZhbHVlOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSBuOyBpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlcyA9IE1hdGguTWF4KHJlcywgdVtpXSArIHlzW24taWR4MltuIC1pXV0gLSB5c1tpZHgxW2ldXSArIHZbbi1pXSk7CiAgICAgICAgICAgICAgICAvL0NvbnNvbGUuV3JpdGVMaW5lKCJ7MH0oezF9KSAtIHsyfSh7M30pIiwgeXNbbiAtIGlkeDJbbiAtIGldXSwgbiAtIGlkeDJbbi1pXSwgeXNbaWR4MVtpXV0sIGlkeDFbaV0pOwogICAgICAgICAgICAgICAgLy9Db25zb2xlLldyaXRlTGluZSgidTogezB9LCB2OiB7MX0iLCB1W2ldLCB2W24taV0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybiByZXM7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgc3RhdGljIHZvaWQgTWFpKCkKICAgICAgICB7CiAgICAgICAgICAgIGludCBuID0gUmVhZEludCgpOwogICAgICAgICAgICBpbnRbXSBzZXEgPSBSZWFkSW50cygpOwogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzb2x2ZShuLHNlcSkpOwogICAgICAgIH0KICAgIH0KfQo=