Yuki có một dãy số $a$ có độ dài $n$.

Yuki định nghĩa một thao tác như sau:

• Chọn một đoạn $[l, r]$ có độ dài chẵn. Với mỗi số nguyên $i$ thỏa mãn $l \le i \le r$:
  • Nếu $i - l$ là số lẻ, giá trị của $a_i$ giảm đi $1$, tức là $a_i \leftarrow a_i - 1$.
  • Nếu $i - l$ là số chẵn, giá trị của $a_i$ tăng thêm $1$, tức là $a_i \leftarrow a_i + 1$.

Bây giờ, Yuki muốn thực hiện một số thao tác sao cho tất cả các số trong dãy $a$ đều bằng nhau. Bạn cần giúp Yuki tìm số thao tác ít nhất cần thiết để làm cho tất cả các số trong dãy $a$ bằng nhau, hoặc cho biết nếu điều đó là không thể.

Dữ liệu vào

Bài toán này có nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên dương $t$ ($1 \le t \le 10^5$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa một số nguyên dương $n$ ($1 \le n \le 10^6$).
• Dòng thứ hai chứa $n$ số nguyên $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng:

• Nếu không thể thực hiện được, in ra $-1$.
• Nếu có thể, in ra một số nguyên biểu thị số thao tác ít nhất để làm cho tất cả các số trong dãy $a$ bằng nhau.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
2
-1

Giải thích

Đối với bộ dữ liệu đầu tiên:

• Thực hiện thao tác trên đoạn $[1, 2]$. Dãy số trở thành $2, 2$, tất cả các số đều bằng nhau.
• Có thể chứng minh rằng không tồn tại cách nào dùng ít thao tác hơn, vì vậy đáp án là $1$.

Đối với bộ dữ liệu thứ hai:

• Thực hiện thao tác trên đoạn $[1, 4]$. Dãy số trở thành $2, 4, 2, 4$.
• Thực hiện thao tác trên đoạn $[1, 4]$. Dãy số trở thành $3, 3, 3, 3$, tất cả các số đều bằng nhau.
• Có thể chứng minh rằng không tồn tại cách nào dùng ít thao tác hơn, vì vậy đáp án là $2$.

Đối với bộ dữ liệu thứ ba:

• Dễ dàng chứng minh rằng không thể làm cho tất cả các số bằng nhau bất kể thực hiện bao nhiêu thao tác, vì vậy đáp án là $-1$.