בצורת ייבשה את הדשא של Farmer John. אחרי שעות ייאוש והרהור, עולה הרעיון המבריק לקנות תירס לפרות היקרות.

$N$ פרות ($1\le N\le10^5$) בשורה, רעב $h_i$ ($0\le h_i\le10^9$). חברתיות ומתעקשות לאכול יחד: הדרך היחידה לתת לשכנות $i,i+1$ שק לכל אחת, ולהקטין כל רעב באחד.

רוצה רעב שווה ולא שלילי לכולן. מצאו מינימום שקים, או -1 אם בלתי אפשרי.

קלט

כמה מקרים עצמאיים, כולם חייבים להיפתר נכון. תחילה $T$ ($1\le T\le100$), אז שתי שורות לכל מקרה: $N$, $h_1,h_2,\ldots,h_N$. סכום $N$ עד $10^5$, ה־$N$ עשויים להשתנות.

פלט

$T$ שורות, אחת לכל מקרה.

ערכים גדולים עשויים לדרוש 64 סיביות, למשל C/C++ long long.

דוגמאות

קלט 1

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

פלט 1

14
16
-1
-1
-1

Note

בראשון שני שקים לכל אחת מ־2,3 ואז חמישה לכל אחת מ־1,2: רעב כולן 3.

בשני שניים לכל אחת מ־1,2, מ־2,3, מ־4,5 ומ־5,6: רעב כולן 2.

בשאר אי אפשר להשוות רעב.

תתי־משימות

• כל מקרי קלט 2: $N\le3$, $h_i\le100$.
• כל מקרי 3–8: $N\le100$, $h_i\le100$.
• כל מקרי 9–14: $N\le100$.
• קלט 15 ללא מגבלות נוספות.

בנוסף $N$ תמיד זוגי ב־3–5 ו־9–11, אי־זוגי ב־6–8 ו־12–14.

מחבר הבעיה: Arpan Banerjee