题解

题面描述

小红有一个长度为 $n$ 的魔法环，环上依次有数字 $a_1, a_2, \dots, a_n$。她想通过切开并对线性序列应用交替求和，获得最佳魔法值，具体操作如下：

1. 选定一个断开位置 $k\ (1 \le k \le n)$，将环从此位置切开，得到线性序列：

2. 根据线性序列 ${b_j}$ 计算其交替求和：

题目内容

小红有一个长度为 $n$ 的魔法环，环上依次有数字 $a_1,a_2,…,a_n$ 。 她想通过切开并对线性序列应用交替求和，获得最佳魔法值具体步骤：

1.选定一个断开位置 $k (1≤k≤n)$ ，循环从此位置切开，得到线性序列

$b_1=a_k,b_2=a_{k+1},…, b_ {n-k+1}=a_n$,$b_{n-k+1}=a_n$,$b_{n-k+2}=a_1$$,...,$$b_n=a_{k-1}$。

2.根据线性序列{$b_j$}计算其交替求和：$S = b_1 - b_2 + b_3 - b_4 + … + (-1)^{n-1}b_n$ 。

小红希望在所有可能的断开位置中，$S$ 的值最大。请你计算并输出此最大值。

输入描述

第一行输入一个整数 $n (1≤n≤2×10^5)$，表示魔法环上的数字个数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n (0≤a_i< n)$ ，代表环上各位置的初始数字。

输出描述

输出一个整数，表示小红在所有断开位置的交替求和中能获得的最大魔法值。

样例1

输入

4
1 2 3 2

输出

0

说明

对于任意断开位置，线性序列的交替求和均为 $0$ 。

样例2

输入

6
1 2 3 2 5 0

输出

5

说明

当断开位置 $k = 1$ 时，序列 $[1,2,3,2,5,0]$ 的交替求和为 $1-2+3-2+5-0=5$ ，是所有位置中的最大值。