#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(){

    // ios::sync_with_stdio(false);

    #ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif
    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];
                // cout<<"j(<=): "<<j<<endl;
                // cout<<rp[j]<<" "<<rp[j+1]<<endl;
                // cout<<rt[j]<<" "<<rt[j+1]<<endl;
            }
            else{
                // cout<<"j(>): "<<j<<endl;
                // cout<<a[j]<<" "<<rp[j+1]<<endl;
                // cout<<rp[j]<<" "<<rp[j+1]<<endl;
                // cout<<rt[j]<<" "<<rt[j+1]<<endl;
                rp[j] = a[j] - rp[j+1];
                rt[j] = a[j] - rp[j+1] + rt[j+1];
            }
        }
        // cout<<"lt"<<endl;
        // for(int j=1; j<=n; j++) cout << lt[j] <<"\t";
        // cout<<endl;
        // cout<<"lp"<<endl;
        // for(int j=1; j<=n; j++) cout << lp[j] <<"\t";
        // cout<<endl;
        // cout<<"rt"<<endl;
        // for(int j=1; j<=n; j++) cout << rt[j] <<"\t";
        // cout<<endl;
        // cout<<"rp"<<endl;
        // for(int j=1; j<=n; j++) cout << rp[j] <<"\t";
        // cout<<endl;

        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;
    }
    return 0;
}