Юкиде ұзындығы $n$ болатын $a$ тізбегі бар.

Юки амалды келесідей анықтайды:

• Ұзындығы жұп болатын $[l, r]$ кесіндісін таңдаңыз. $l \le i \le r$ шартын қанағаттандыратын әрбір бүтін $i$ үшін:
  • Егер $i - l$ тақ болса, $a_i$ мәні $1$-ге кемиді, яғни $a_i \leftarrow a_i - 1$.
  • Егер $i - l$ жұп болса, $a_i$ мәні $1$-ге артады, яғни $a_i \leftarrow a_i + 1$.

Енді Юки $a$ тізбегіндегі барлық сандар тең болатындай етіп бірнеше амал орындағысы келеді. Сіз Юкиге $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$.