ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Sasha Vilkin

Time limit: 1.0 second
Memory limit: 256 MB
Sasha Vilkin wants to eat, since his fullness level dropped to 0. In this case, he goes to his favorite fast food restaurant — “Lilka Vozhka”. This is his most loved place to be, because as soon as he goes inside, he enters a magical world, where food is different than it is anywhere else...
Every meal in this wonderful place has its own nutrition, which is an integer value. When Sasha eats a meal of nutrition a, his fullness increases by a. In this magical world food can even have negative nutrition. Unfortunately, Sasha’s stomach can’t handle it when Sasha eats multiple meals in a row. When he eats several meals, each odd meal is digested normally, increasing Sasha’s fullness by it’s nutrition value; but each even meal doesn’t digest well, so it decreases Sasha’s fullness by it’s nutrition value.
There are n meals in the restaurant, placed on a counter in a row from left to right. They are numbered from 1 to n in the order they are placed. Meal number i has nutrition ai. Sasha is in too much of a hurry to think about what to choose, so he will just buy several meals placed in a row (or buy none at all). After the choice is made, Sasha will eat them in the order they are placed, and then eat no more. Help Sasha to determine the maximal level of fullness he can attain.
More formally: you are given a sequence of integers ai. You need to choose a continuous segment of the sequence (an empty segment is also allowed), the alternating sum of which is maximal possible. Alternating sum of sequence al, al + 1, al + 2, …, ar is equal to alal + 1 + al + 2 − … + (−1)rl ar.

Input

The first line contains one integer n — amount of meals in the restaurant (1 ≤ n ≤ 105).
The second line contains n space-separated integers ai — nutritions of meals (−105ai ≤ 105).

Output

Output one integer — the maximal fullness of Sasha after he finishes eating. Keep in mind that he may eat nothing to attain the maximal possible fullness.

Samples

inputoutput
5
1 2 3 4 5
5
5
1 -2 3 -4 5
15
5
-1 -2 -3 -4 -5
2

Notes

In the first example, it’s better for Sasha to take the fifth meal, and his fullness level will be equal to 5.
In the second example, Sasha can take all the meals, then the alternating sum of nutritions will be equal to 15.
In the third example, Sasha can take either the first four meals or the last four meals, in both cases the alternating sum of nutritions will be equal to 2.
Problem Author: Alexander Lozhkin
To submit the solution for this problem go to the Problem set: 2141. Sasha Vilkin