CF2140C Ultimate Value

Let's define a function $f(a)$ for an array $a$ of length $n$ as $$ f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n) $$ where $\textrm{cost}$ is zero initially. Now consider the scenario where Alice and Bob are given an array $a$ of length $n$. They play a game taking at most $10^{100}$ turns alternately with Alice going first. In each turn, they must perform any **one** (only one) of the following operations: - End the game for both Alice and Bob. - Choose two indices $l,r$ with $1 \le l \le r \le n$ and swap $a_l$ and $a_r$; this adds $(r - l)$ to the $\textrm{cost}$. Assume that Alice tries to maximize $f(a)$ and Bob tries to minimize it. Your task is to determine the final value of $f(a)$ assuming both players play optimally.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$. The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

For each testcase, output a single integer — the final value of $f(a)$ assuming both players play optimally.

For the first testcase, it is optimal for Alice to end the game on her first turn. So the final value of $\textrm{cost} = 0$ and $f(a) = 0 + 1000 - 1 = 999$. For the fourth testcase, it is optimal for Alice to swap $a_1$ and $a_6$, and then it is optimal for Bob to end the game on his first turn. So the final value of $\textrm{cost} = 5$ and $f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$.