解题思路

我们需要在一个环形灯阵中，选定任意一盏灯作为起点，顺时针得到一个长度为 $n$ 的线性序列 $b_1, \dots, b_n$ ，并计算交错和

S = b_1 - b_2 + b_3 - b_4 + \cdots + (-1)^{n-1} b_n

求所有可能起点的 $S$ 的最大值。

直接对每一个起点单独计算交错和的复杂度为 $O(n^2)$ ，在 $n \le 2\times 10^5$ 时无法满足要求。可以利用递推关系在 $O(1)$ 时间内从一个起点的交错和转移到顺时针下一个起点的交错和。

设 $S_k$ 表示从第 $k$ 个位置作为起点时的交错和（这里位置下标按输入顺序从 $1$ 到 $n$ 记，即 $S_1$ 对应起点 $a_1$ ）。我们可以先计算出 $S_1$ 的值，然后推导 $S_{k+1}$ 与 $S_k$ 的关系：

题目内容

小蓝有一个环形灯阵，灯阵上依次排列着 n 盏灯。每盏灯都有一个非负整数亮度值，按顺时针顺序记为 $a_1, a_2, \dots, a_n$ 。她想通过以下方式计算灯阵的“交错能量”：

小蓝希望知道，在所有可能的起点中，交错和 $S$ 的最大值是多少。请你输出这个最大值。

约束条件：灯的数量 $n$ 满足 $1 \le n \le 2 \times 10^5$ ；每盏灯的亮度 $a_i$ 满足 $0 \le a_i < n$ 。