The vacation started, and Lutfi asked his friend to give him a list of movies to watch during his vacation.

Lutfi's friend has a list with $n$ movie ratings, the $i^{th}$ movie has a rating $a_i$

Lutfi is going to choose two indices $i$ and $j$, such that $i \leq j$ and $j \leq n$, and watch the movies with ratings $a_i, a_{i + 1}, a_{i + 2}, ..., a_j$.

After he finishes watching the movies, Lutfi's happiness will be equal to the sum of the ratings of the movies that he chose to watch. Your task is to find the maximum happiness that Lutfi can achieve, assuming that he chooses $i$ and $j$ optimally.

Of course, Lutfi will watch at least one movie so his friend doesn't get mad at him.

The first line of input contains a single integer $n$, the number of movies in list ($1 \leq n \leq 10^6$).

The next line contains $n$ space-separated integers $a_1, a_2, ..., a_n$, the rating of each movie ($-10^6 \leq a_i \leq 10^6$).

Output a single integer $k$, the maximum happiness that Lutfi can achieve.