Yuki er með runu $a$ af lengd $n$.

Yuki skilgreinir aðgerð sem hér segir:

• Veldu bil $[l, r]$ af sléttri lengd. Fyrir sérhverja heiltölu $i$ þannig að $l \le i \le r$:
  • Ef $i - l$ er oddatala minnkar gildið á $a_i$ um $1$, þ.e. $a_i \leftarrow a_i - 1$.
  • Ef $i - l$ er slétt tala hækkar gildið á $a_i$ um $1$, þ.e. $a_i \leftarrow a_i + 1$.

Nú vill Yuki framkvæma nokkrar aðgerðir þannig að allar tölurnar í rununni $a$ verði jafnar. Þú þarft að hjálpa Yuki að finna lágmarksfjölda aðgerða sem þarf til að gera allar tölurnar í rununni $a$ jafnar, eða tilkynna ef það er ómögulegt.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik.

Fyrsta línan inniheldur jákvæða heiltölu $t$ ($1 \le t \le 10^5$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur jákvæða heiltölu $n$ ($1 \le n \le 10^6$).
• Önnur línan inniheldur $n$ heiltölur $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu:

• Ef það er ómögulegt skal prenta út $-1$.
• Ef það er mögulegt skal prenta út heiltölu sem táknar lágmarksfjölda aðgerða til að gera allar tölurnar í rununni $a$ jafnar.

Dæmi

Inntak 1

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

Úttak 1

1
2
-1

Athugasemd

Fyrir fyrsta prófunartilvikið:

• Framkvæmið aðgerðina á bilinu $[1, 2]$. Runan verður $2, 2$, þar sem allar tölurnar eru jafnar.
• Sanna má að engin lausn með færri aðgerðum sé til, svo svarið er $1$.

Fyrir annað prófunartilvikið:

• Framkvæmið aðgerðina á bilinu $[1, 4]$. Runan verður $2, 4, 2, 4$.
• Framkvæmið aðgerðina á bilinu $[1, 4]$. Runan verður $3, 3, 3, 3$, þar sem allar tölurnar eru jafnar.
• Sanna má að engin lausn með færri aðgerðum sé til, svo svarið er $2$.

Fyrir þriðja prófunartilvikið:

• Auðvelt er að sanna að ómögulegt sé að gera allar tölurnar jafnar óháð fjölda aðgerða, svo svarið er $-1$.