Description

一天，主人买来N个BONE(1 <= N <= 150,000)，从左向右排成一排. 狗狗想把所有的BONE全吃了，但这似乎不太可能的.主人说：狗狗，你做为我的宠物,应该要足够的聪明伶俐，睿智过人，玉树临风.我来考一下你.这里每一个BONE都有一个分数K(1<=K<=500)。你从第一个BONE开始.对于每个BONE，你可选也可不选。选择多少个也随便你但你必须从第一个开始选，从左选到右。当你选好BONE后。我会将第一个BONE的分值乘上一个1,第二个则乘上一个-1第三个又是一个1,第四个又是一个-1.然后再加起来。我希望总分值最大。你应该如何选呢

Format

Input

第一行给出一个数字N，代表有多少块Bone. 下面N行，每行一个数字，代表每块Bone的权值。

Output

如题

Samples

8
7
2
1
8
4
3
5
6

17

3
10
2
2

10

Hint

取7 1 8 3 6，得到+7-1+8-3+6=17。