Yuki memiliki sebuah barisan $a$ dengan panjang $n$.

Yuki mendefinisikan sebuah operasi sebagai berikut:

• Pilih sebuah interval $[l, r]$ dengan panjang genap. Untuk setiap bilangan bulat $i$ sedemikian sehingga $l \le i \le r$:
  • Jika $i - l$ ganjil, nilai $a_i$ berkurang sebesar $1$, yaitu $a_i \leftarrow a_i - 1$.
  • Jika $i - l$ genap, nilai $a_i$ bertambah sebesar $1$, yaitu $a_i \leftarrow a_i + 1$.

Sekarang, Yuki ingin melakukan sejumlah operasi sehingga semua bilangan di dalam barisan $a$ bernilai sama. Anda perlu membantu Yuki mencari banyaknya operasi minimum yang diperlukan untuk membuat semua bilangan di dalam barisan $a$ bernilai sama, atau melaporkan jika hal tersebut tidak mungkin.

Format Masukan

Soal ini berisi beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat positif $t$ ($1 \le t \le 10^5$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi sebuah bilangan bulat positif $n$ ($1 \le n \le 10^6$).
• Baris kedua berisi $n$ bilangan bulat $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $10^6$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris:

• Jika tidak mungkin, keluarkan $-1$.
• Jika mungkin, keluarkan sebuah bilangan bulat yang menyatakan banyaknya operasi minimum untuk membuat semua bilangan di dalam barisan $a$ bernilai sama.

Contoh

Masukan 1

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

Keluaran 1

1
2
-1

Catatan

Untuk kasus uji pertama:

• Lakukan operasi pada interval $[1, 2]$. Barisan menjadi $2, 2$, dengan semua bilangan bernilai sama.
• Dapat dibuktikan bahwa tidak ada solusi dengan operasi yang lebih sedikit, sehingga jawabannya adalah $1$.

Untuk kasus uji kedua:

• Lakukan operasi pada interval $[1, 4]$. Barisan menjadi $2, 4, 2, 4$.
• Lakukan operasi pada interval $[1, 4]$. Barisan menjadi $3, 3, 3, 3$, dengan semua bilangan bernilai sama.
• Dapat dibuktikan bahwa tidak ada solusi dengan operasi yang lebih sedikit, sehingga jawabannya adalah $2$.

Untuk kasus uji ketiga:

• Mudah dibuktikan bahwa tidak mungkin membuat semua bilangan bernilai sama berapa pun banyaknya operasi yang dilakukan, sehingga jawabannya adalah $-1$.