Yuki มีลำดับ $a$ ที่มีความยาว $n$

Yuki นิยามการดำเนินการดังต่อไปนี้:

• เลือกช่วง $[l, r]$ ที่มีความยาวเป็นจำนวนคู่ สำหรับแต่ละจำนวนเต็ม $i$ ที่ $l \le i \le r$:
  • หาก $i - l$ เป็นจำนวนคี่ ค่าของ $a_i$ จะลดลง $1$ นั่นคือ $a_i \leftarrow a_i - 1$
  • หาก $i - l$ เป็นจำนวนคู่ ค่าของ $a_i$ จะเพิ่มขึ้น $1$ นั่นคือ $a_i \leftarrow a_i + 1$

ตอนนี้ Yuki ต้องการทำการดำเนินการจำนวนหนึ่งเพื่อให้ตัวเลขทั้งหมดในลำดับ $a$ มีค่าเท่ากัน คุณต้องช่วย Yuki หาจำนวนครั้งของการดำเนินการที่น้อยที่สุดที่ต้องใช้เพื่อทำให้ตัวเลขทั้งหมดในลำดับ $a$ เท่ากัน หรือรายงานว่าเป็นไปไม่ได้

ข้อมูลนำเข้า

ปัญหานี้ประกอบด้วยหลายชุดข้อมูลทดสอบ

บรรทัดแรกประกอบด้วยจำนวนเต็มบวก $t$ ($1 \le t \le 10^5$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ:

• บรรทัดแรกประกอบด้วยจำนวนเต็มบวก $n$ ($1 \le n \le 10^6$)
• บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$)

รับประกันว่าผลรวมของ $n$ ในทุกชุดข้อมูลทดสอบไม่เกิน $10^6$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัด:

• หากเป็นไปไม่ได้ ให้แสดงผล $-1$
• หากเป็นไปได้ ให้แสดงผลจำนวนเต็มที่แทนจำนวนครั้งของการดำเนินการที่น้อยที่สุดที่จะทำให้ตัวเลขทั้งหมดในลำดับ $a$ เท่ากัน

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

1
2
-1

หมายเหตุ

สำหรับชุดข้อมูลทดสอบแรก:

• ทำการดำเนินการบนช่วง $[1, 2]$ ลำดับจะกลายเป็น $2, 2$ ซึ่งตัวเลขทั้งหมดมีค่าเท่ากัน
• สามารถพิสูจน์ได้ว่าไม่มีวิธีการที่ใช้จำนวนครั้งน้อยกว่านี้ ดังนั้นคำตอบคือ $1$

สำหรับชุดข้อมูลทดสอบที่สอง:

• ทำการดำเนินการบนช่วง $[1, 4]$ ลำดับจะกลายเป็น $2, 4, 2, 4$
• ทำการดำเนินการบนช่วง $[1, 4]$ ลำดับจะกลายเป็น $3, 3, 3, 3$ ซึ่งตัวเลขทั้งหมดมีค่าเท่ากัน
• สามารถพิสูจน์ได้ว่าไม่มีวิธีการที่ใช้จำนวนครั้งน้อยกว่านี้ ดังนั้นคำตอบคือ $2$

สำหรับชุดข้อมูลทดสอบที่สาม:

• สามารถพิสูจน์ได้โดยง่ายว่าเป็นไปไม่ได้ที่จะทำให้ตัวเลขทั้งหมดเท่ากันไม่ว่าจะทำการดำเนินการกี่ครั้งก็ตาม ดังนั้นคำตอบคือ $-1$