가뭄으로 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