Yuki har en følge $a$ av lengde $n$.

Yuki definerer en operasjon som følger:

• Velg et intervall $[l, r]$ med partallslengde. For hvert heltall $i$ slik at $l \le i \le r$:
  • Hvis $i - l$ er odde, reduseres verdien av $a_i$ med $1$, dvs. $a_i \leftarrow a_i - 1$.
  • Hvis $i - l$ er partall, økes verdien av $a_i$ med $1$, dvs. $a_i \leftarrow a_i + 1$.

Nå ønsker Yuki å utføre et visst antall operasjoner slik at alle tallene i følgen $a$ blir like. Du må hjelpe Yuki med å finne det minste antallet operasjoner som kreves for å gjøre alle tallene i følgen $a$ like, eller rapportere hvis det er umulig.

Inndata

Dette problemet inneholder flere testtilfeller.

Den første linjen inneholder et positivt heltall $t$ ($1 \le t \le 10^5$), som representerer antall testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder et positivt heltall $n$ ($1 \le n \le 10^6$).
• Den andre linjen inneholder $n$ heltall $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut én linje:

• Hvis det er umulig, skriv ut $-1$.
• Hvis det er mulig, skriv ut et heltall som representerer det minste antallet operasjoner for å gjøre alle tallene i følgen $a$ like.

Eksempler

Inndata 1

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

Utdata 1

1
2
-1

Merk

For det første testtilfellet:

• Utfør operasjonen på intervallet $[1, 2]$. Følgen blir $2, 2$, der alle tallene er like.
• Det kan bevises at det ikke finnes noen løsning med færre operasjoner, så svaret er $1$.

For det andre testtilfellet:

• Utfør operasjonen på intervallet $[1, 4]$. Følgen blir $2, 4, 2, 4$.
• Utfør operasjonen på intervallet $[1, 4]$. Følgen blir $3, 3, 3, 3$, der alle tallene er like.
• Det kan bevises at det ikke finnes noen løsning med færre operasjoner, så svaret er $2$.

For det tredje testtilfellet:

• Det er lett å bevise at det er umulig å gjøre alle tallene like uansett antall operasjoner, så svaret er $-1$.