#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
long long t,n;
long long a[MAXN], lt[MAXN], lp[MAXN], rt[MAXN], rp[MAXN];

int main(){
    long long time = 0, minn = 1e15+1;
    cin >> t;
    for(int i=1;i<=t;i++){
        cin>>n;
        memset(a,0,sizeof(a));
        memset(lt,0,sizeof(lt));
        memset(lp,0,sizeof(lp));
        memset(rt,0,sizeof(rt));
        memset(rp,0,sizeof(rp));
        for(int j=1;j<=n;j++){
            cin>>a[j];         
        }
        for(int j=1;j<=n;j++){
            if(a[j]<=lp[j-1]){
                lp[j] = a[j];
                lt[j] = lt[j-1];
            }
            else{
                lp[j] = a[j] - lp[j-1];
                lt[j] = a[j] - lp[j-1] + lt[j-1];
            }
        }

        for(int j=n;j>=1;j--){
            if(a[j]<=rp[j+1]){
                rp[j] = a[j];
                rt[j] = rt[j+1];
            }
            else{
                rp[j] = a[j] - rp[j+1];
                rt[j] = a[j] - rp[j+1] + rt[j+1];
            }
        }

        for(int j=1;j<=n;j++){
            if(j==1){
                time = rt[j];
            }
            else if(j==n){
                time = lt[j];
            }
            else{
                if(lp[j-1] >= a[j] || rp[j+1] >=a[j]){
                    time = lt[j-1] + rt[j+1];
                }
                else{
                    time = lt[j-1] + rt[j+1] + a[j] - max(lp[j-1],rp[j+1]);
                }
            }
            minn = min(time, minn);
        }
        cout<<minn<<endl;
        minn = 1e15+1;
        time = 0;
    }
    return 0;
}