달리는 게임

일직선을 달려가면서 점수가 붙은 물체를 차례로 먹는 게임이 요즘 유행이다. 유행을 조금 늦게 따라가는 경근이도 이런 게임을 하나 만들었다. 이름은 아직 없다.

이 게임에는 물체를 먹을 때마다 점수에 곱해지는 곱 계수가 있다. 게임을 시작할 때 곱 계수는 0이다. 캐릭터는 아주 먼 왼쪽의 한 지점에서 출발해 오른쪽으로 달려가고, 경근이가 일직선 위에 놓아둔 물체를 순서대로 만난다. 캐릭터가 물체를 먹으면 곱 계수가 1 늘어난 다음, (먹은 물체의 점수) $\times$ (늘어난 곱 계수)만큼이 캐릭터가 얻은 점수에 더해진다. 물체를 먹지 않으면 곱 계수가 0으로 초기화되고 점수도 얻지 못한다. 물체의 점수가 양수라는 보장이 없으므로, 높은 점수를 받으려면 어떤 물체를 먹고 어떤 물체를 건너뛸지 잘 정해야 한다. 이를 정하고 나면 캐릭터는 다시 오른쪽으로 달리며, 왼쪽으로 되돌아갈 수는 없다.

경근이가 만든 맵에서 캐릭터는 물체 $N$개를 순서대로 만난다. 물체의 점수가 놓인 순서대로 주어질 때, 캐릭터가 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 자연수 $N$ ($1 \le N \le 10^6$)이 주어진다.

둘째 줄에 물체의 점수를 뜻하는 정수 $N$개가 공백을 사이에 두고 주어진다. 물체는 맵에 놓인 순서대로 주어지므로 캐릭터도 주어진 순서대로 물체를 만난다. 각 정수의 절댓값은 $10^6$ 이하이다.

주어진 맵에서 캐릭터가 얻을 수 있는 최대 점수를 출력한다. 답은 32비트 정수의 범위를 넘을 수 있으므로 64비트 정수를 쓴다.

첫 번째 예제에서는 세 물체를 모두 먹는 것이 최선이다.

• 세 번째 물체만 먹으면 $5 \times 1 = 5$점이다.
• 두 번째와 세 번째 물체를 먹으면 $(-1) \times 1 + 5 \times 2 = 9$점이다.
• 세 물체를 모두 먹으면 $(-1) \times 1 + (-1) \times 2 + 5 \times 3 = 12$점이다.