Yuki hat eine Folge $a$ der Länge $n$.

Yuki definiert eine Operation wie folgt:

• Wähle ein Intervall $[l, r]$ mit gerader Länge. Für jede ganze Zahl $i$ mit $l \le i \le r$:
  • Falls $i - l$ ungerade ist, verringert sich der Wert von $a_i$ um $1$, d. h. $a_i \leftarrow a_i - 1$.
  • Falls $i - l$ gerade ist, erhöht sich der Wert von $a_i$ um $1$, d. h. $a_i \leftarrow a_i + 1$.

Nun möchte Yuki einige Operationen durchführen, sodass alle Zahlen in der Folge $a$ gleich sind. Du musst Yuki helfen, die minimale Anzahl an Operationen zu finden, die nötig ist, um alle Zahlen in der Folge $a$ gleich zu machen, oder mitteilen, dass dies unmöglich ist.

Eingabe

Dieses Problem enthält mehrere Testfälle.

Die erste Zeile enthält eine positive ganze Zahl $t$ ($1 \le t \le 10^5$), die die Anzahl der Testfälle angibt.

Für jeden Testfall:

• Die erste Zeile enthält eine positive ganze Zahl $n$ ($1 \le n \le 10^6$).
• Die zweite Zeile enthält $n$ ganze Zahlen $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile aus:

• Falls es unmöglich ist, gib $-1$ aus.
• Falls es möglich ist, gib eine ganze Zahl aus, die die minimale Anzahl an Operationen darstellt, um alle Zahlen in der Folge $a$ gleich zu machen.

Beispiele

Eingabe 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

Ausgabe 1

1
2
-1

Hinweis

Für den ersten Testfall:

• Führe die Operation auf dem Intervall $[1, 2]$ aus. Die Folge wird zu $2, 2$, wobei alle Zahlen gleich sind.
• Es lässt sich beweisen, dass keine Lösung mit weniger Operationen existiert, also lautet die Antwort $1$.

Für den zweiten Testfall:

• Führe die Operation auf dem Intervall $[1, 4]$ aus. Die Folge wird zu $2, 4, 2, 4$.
• Führe die Operation auf dem Intervall $[1, 4]$ aus. Die Folge wird zu $3, 3, 3, 3$, wobei alle Zahlen gleich sind.
• Es lässt sich beweisen, dass keine Lösung mit weniger Operationen existiert, also lautet die Antwort $2$.

Für den dritten Testfall:

• Es ist leicht zu beweisen, dass es unabhängig von der Anzahl der Operationen unmöglich ist, alle Zahlen gleich zu machen, also lautet die Antwort $-1$.