P17294 [ICPC 2026 Xi'an I] North and South

Yuki has a sequence $a$ of length $n$. Yuki defines an operation as follows: - Choose an interval $[l, r]$ of $\textbf{even length}$. For every integer $i$ such that $l \le i \le r$: - If $i-l$ is odd, the value of $a_i$ decreases by $1$, i.e., $a_i \gets a_i-1$. - If $i-l$ is even, the value of $a_i$ increases by $1$, i.e., $a_i \gets a_i+1$. Now, Yuki wants to perform some number of operations such that all numbers in the sequence $a$ are equal. You need to help Yuki find the minimum number of operations required to make all numbers in the sequence $a$ equal, or report if it is impossible.

This problem contains multiple test cases. The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases. For each test case: - The first line contains a positive integer $n$ $(1 \le n \le 10^6)$. - The second line contains $n$ integers $a_1, \dots, a_n$ $(0 \le a_i \le 10^{12})$. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one line: - If it is impossible, output $-1$. - If it is possible, output an integer representing the minimum number of operations to make all numbers in the sequence $a$ equal.

For the first test case: - Perform the operation on the interval $[1, 2]$. The sequence becomes $2, 2$, where all numbers are equal. - It can be proven that no solution with fewer operations exists, so the answer is $1$. For the second test case: - Perform the operation on the interval $[1, 4]$. The sequence becomes $2, 4, 2, 4$. - Perform the operation on the interval $[1, 4]$. The sequence becomes $3, 3, 3, 3$, where all numbers are equal. - It can be proven that no solution with fewer operations exists, so the answer is $2$. For the third test case: - It is easy to prove that it is impossible to make all numbers equal regardless of the number of operations, so the answer is $-1$.