Yukilla on pituutta $n$ oleva lukujono $a$.

Yuki määrittelee operaation seuraavasti:

• Valitse parillisen pituinen väli $[l, r]$. Jokaiselle kokonaisluvulle $i$, jolle $l \le i \le r$:
  • Jos $i - l$ on pariton, luvun $a_i$ arvo pienenee yhdellä ($1$), eli $a_i \leftarrow a_i - 1$.
  • Jos $i - l$ on parillinen, luvun $a_i$ arvo kasvaa yhdellä ($1$), eli $a_i \leftarrow a_i + 1$.

Nyt Yuki haluaa suorittaa joitakin operaatioita niin, että kaikki lukujonon $a$ luvut ovat yhtä suuria. Sinun tulee auttaa Yukia löytämään pienin operaatioiden määrä, jolla kaikki lukujonon $a$ luvut saadaan yhtä suuriksi, tai ilmoittaa, jos se on mahdotonta.

Syöte

Tässä tehtävässä on useita testitapauksia.

Ensimmäinen rivi sisältää positiivisen kokonaisluvun $t$ ($1 \le t \le 10^5$), joka ilmoittaa testitapausten määrän.

Jokaiselle testitapaukselle:

• Ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$ ($1 \le n \le 10^6$).
• Toinen rivi sisältää $n$ kokonaislukua $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi:

• Jos se on mahdotonta, tulosta $-1$.
• Jos se on mahdollista, tulosta kokonaisluku, joka ilmoittaa pienimmän operaatioiden määrän, jolla kaikki lukujonon $a$ luvut saadaan yhtä suuriksi.

Esimerkit

Syöte 1

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

Tuloste 1

1
2
-1

Huomautus

Ensimmäisessä testitapauksessa:

• Suoritetaan operaatio välillä $[1, 2]$. Lukujonoksi tulee $2, 2$, jolloin kaikki luvut ovat yhtä suuria.
• Voidaan todistaa, ettei pienemmällä operaatiomäärällä ole ratkaisua, joten vastaus on $1$.

Toisessa testitapauksessa:

• Suoritetaan operaatio välillä $[1, 4]$. Lukujonoksi tulee $2, 4, 2, 4$.
• Suoritetaan operaatio välillä $[1, 4]$. Lukujonoksi tulee $3, 3, 3, 3$, jolloin kaikki luvut ovat yhtä suuria.
• Voidaan todistaa, ettei pienemmällä operaatiomäärällä ole ratkaisua, joten vastaus on $2$.

Kolmannessa testitapauksessa:

• On helppo todistaa, että kaikkia lukuja on mahdotonta saada yhtä suuriksi operaatioiden määrästä riippumatta, joten vastaus on $-1$.