Yuki har en talföljd $a$ av längd $n$.

Yuki definierar en operation enligt följande:

• Välj ett intervall $[l, r]$ av jämn längd. För varje heltal $i$ sådant att $l \le i \le r$:
  • Om $i - l$ är udda minskar värdet på $a_i$ med $1$, dvs. $a_i \leftarrow a_i - 1$.
  • Om $i - l$ är jämnt ökar värdet på $a_i$ med $1$, dvs. $a_i \leftarrow a_i + 1$.

Nu vill Yuki utföra ett antal operationer så att alla tal i talföljden $a$ blir lika. Du ska hjälpa Yuki att hitta det minsta antalet operationer som krävs för att göra alla tal i talföljden $a$ lika, eller rapportera om det är omöjligt.

Indata

Detta problem innehåller flera testfall.

Den första raden innehåller ett positivt heltal $t$ ($1 \le t \le 10^5$), som representerar antalet testfall.

För varje testfall:

• Den första raden innehåller ett positivt heltal $n$ ($1 \le n \le 10^6$).
• Den andra raden innehåller $n$ heltal $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut en rad:

• Om det är omöjligt, skriv ut $-1$.
• Om det är möjligt, skriv ut ett heltal som representerar det minsta antalet operationer för att göra alla tal i talföljden $a$ lika.

Exempel

Indata 1

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

Utdata 1

1
2
-1

Notering

För det första testfallet:

• Utför operationen på intervallet $[1, 2]$. Talföljden blir $2, 2$, där alla tal är lika.
• Det kan bevisas att det inte finns någon lösning med färre operationer, så svaret är $1$.

För det andra testfallet:

• Utför operationen på intervallet $[1, 4]$. Talföljden blir $2, 4, 2, 4$.
• Utför operationen på intervallet $[1, 4]$. Talföljden blir $3, 3, 3, 3$, där alla tal är lika.
• Det kan bevisas att det inte finns någon lösning med färre operationer, så svaret är $2$.

För det tredje testfallet:

• Det är lätt att bevisa att det är omöjligt att göra alla tal lika oavsett antalet operationer, så svaret är $-1$.