Drought Bronze

import java.util.*;
public class p3 {
    static class maxmin{
        int max;
        int min;
    }
    public static boolean allsame(int array[]) {
        int n = array.length;
        for(int i = 0; i < n - 1; i++) {
            if(array[i] != array[i + 1]) {
                return false;
            }
            else {
            }
        }
        return true;
    }
    public static boolean noNeg(int arr[]){
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] != Math.abs(arr[i])) {
                return false;
            }
        }
        return true;
    }
    public static maxmin max(int array[]) {
        int n = array.length;
        int max = -1;
        maxmin maxmin = new maxmin();
        int index = -1;
        int min = Integer.MAX_VALUE;
        int ind2 = -1;
        for(int i = 0; i < n; i++) {
            if(max < array[i]) {
                index = i;
                max = array[i];
            }
            if(min > array[i]) {
                ind2 = i;
                min = array[i];
            }
        }
        maxmin.max = index;
        maxmin.min = ind2;
        return maxmin;
    }
    public static void main(String [] args) {
        Scanner scan = new Scanner(System.in);
        int testcases = scan.nextInt();
        for(int testcase = 0; testcase < testcases; testcase++) {
            int n = scan.nextInt();
            int hunger[] = new int[n];
            for(int i = 0; i < n; i++) {
                hunger[i] = scan.nextInt();
            }
            long ans = 0;
            while(!allsame(hunger) && noNeg(hunger)){
                maxmin maxmin = max(hunger);
                int max = maxmin.max;
                int preMin = maxmin.min;
                int min = maxmin.min;
                int preMax = max;
                if(max == 0) {
                    while(min == preMin && noNeg(hunger) && max == preMax){
                        hunger[max]--;
                        hunger[max + 1]--;
                        ans += 2;
                        maxmin = max(hunger);
                        min = maxmin.min;
                        max = maxmin.max;
                    }
                }
                else if(max == n - 1) {
                    while(min == preMin && noNeg(hunger) && max == preMax){
                        hunger[max]--;
                        hunger[max - 1]--;
                        ans+=2;
                        maxmin = max(hunger);
                        max = maxmin.max;
                        min = maxmin.min;
                    }
                }
                else if(max != 0 && max!= n-1){
                    //find largest adjacent node

                    while(min == preMin && noNeg(hunger) && max == preMax) {
                        int ind = 0;
                        if(hunger[max - 1] < hunger[max + 1]) {
                            ind = max + 1;
                        }
                        else {
                            ind = max - 1;
                        }
                        hunger[max]--;
                        hunger[ind]--;
                        maxmin = max(hunger);
                        max = maxmin.max;
                        min = maxmin.min;
                        ans+= 2;
                    }
                }
                if(!noNeg(hunger)) {
                    ans = -1;
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}