جف العشب في مرعى Farmer John بسبب الجفاف. بعد ساعات من اليأس والتأمل، فكّر بشراء الذرة لأبقاره العزيزة كفكرة رائعة.

$N$ أبقار ($1\le N\le10^5$) في صف، جوع $i$ هو $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

ملاحظة

في الأولى كيسان لكل من 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