T580710 「2025 扬大ACM选拔赛」F - Cirno's Circular Sequence

Cirno is given a **circular** integer sequence $a$ of length $n$, the numbers are $a_1, a_2, \ldots, a_n$. In each operation, she can arbitrarily select an index $x$, and let $a_x = a_x - a_{(x \bmod n)+1}$, and then remove $a_{(x \bmod n)+1}$. Finally, there will be just one element left, and Cirno are required to **maximize** this element.

**There are multiple test cases.** The first line of the input contains one integer $T$ —— the number of test cases. **For each test case:** The first line contains one integer $n$ ($1 \le n \le 10^6$) —— the initial length of the **circular** integer sequence. The next line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$) —— the elements of the sequence. It is guaranteed that the $\sum n$ of all test cases will not exceed $10^6$.

**For each test case:** Output one line containing one integer, denoting the maximum possible element.

For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn. $\{ 3, -6, \underline{-2}, \underline{4} \}$ (select $x = 3$) $\to$ $\{ \underline{3}, \underline{-6}, -6 \}$ (select $x = 1$) $\to$ $\{\underline{9}, \underline{-6}\}$ (select $x = 1$) $\to$ $\{\textcolor{blue}{15} \}$.