문제
정올 초원의 모든 풀이 극심한 가뭄으로 다 말라 버렸다.
정올 초원에는 N 마리의 소(1≤N≤105)가 살고 있는데,
이 소들은 일렬로 늘어서 있고, 그 줄의 i번째 소의 배고픔 수준은 hi(0≤hi≤109)이라고 가정하자.
정올 초원의 소들은 매우 사회적인 동물이라 함께 식사를 하기를 고집하기 때문에 소들이 배고픔을 줄일 수 있는 유일한 방법은 인접한 i번째 소와 i+1번째 소가 각각 동시에 옥수수 한 봉지를 먹어 배고픔을 각각 1씩 줄이는 것 뿐이다.
모든 소가 음수가 아닌 동일한 배고픔 수준을 가질 때까지 소가 식사를 한다면 이에 필요한 최소 옥수수 봉지 수가 몇 봉지인지 출력하는 프로그램을 작성하시오.
불가능한 경우 -1을 출력하면 된다.
입력
첫 번째 줄에는 테스트 케이스의 수 T(1≤T≤100)가 입력된다.
각 테스트 케이스 별로 두 줄씩 입력된다.
첫 번째 행은 N, 두 번째 행은 h1,h2,…,hN이 입력된다.
모든 테스트 케이스의 N 합계가 105를 초과하지 않음을 보장한다.
출력
각 테스트 케이스 별로 필요한 최소 옥수수 봉지 수를 출력하시오.
이 문제는 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
출력
14
16
-1
-1
-1
힌트
출처
USACO 2022 January Bronze