badpotato

Problem Description

There are n potatoes on Jiahai's potato farm. Some of them are bad, others are good

Jiahai wants to harvest as much mass of potatos as possible, but he cannot harvest bad potatoes or it will spoil the harvest

The ith potato has a weight wi. Bad potatoes have a weight of -1 while good ones have a positive integer weight

Jiahai's harvestor can only harvest continguous segments of potatos. Can you find the maximum weight of potatoes Jiahai can harvest???

Input

The first line of the input consists of a single integer, n

Next line of input consists of n space separated integers, wi

Output

A single integer w representing the maximum possible weight of potatoes harvested

Subtasks

Subtask 1 (10%) n<=10

Subtask 2 (25%) n<=1000

Subtask 3 (65%) n<=1000000

Subtask 4 (0%) will be the sample testcases

Sample Testcase 1

Input

7
-1 1 2 3 4 5 -1

15

Explanation

Jiahai harvests potatoes 2 to 6

Sample Testcase 2

Input

7
-1 1 2 3 4 -1 5

10

Explanation

Jiahai harvests potatoes 2 to 5