干ばつで 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$ 行、各テスト一行。
大きな値により C/C++ long long など 64 ビット整数が必要かもしれません。
入出力例
入力 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：追加制約なし。
さらに入力 3–5、9–11 の $N$ は常に偶数、6–8、12–14 は常に奇数です。
問題作成：Arpan Banerjee