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 a_i. 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 a_i. 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 a_l, a_{l + 1}, a_{l + 2}, …, a_r is equal to a_l − a_{l + 1} + a_{l + 2} − … + (−1)^{r − l} a_r.

The first line contains one integer n — amount of meals in the restaurant (1 ≤ n ≤ 10⁵).

The second line contains n space-separated integers a_i — nutritions of meals (−10⁵ ≤ a_i ≤ 10⁵).

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.

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.