t=int(input())
while t:
n=int(input())
l=list(map(int,input().split()))
if n==1:
print(l[0])
else:
ans=l[0]+l[-1]
for i in range(1,n):
ans+=abs(l[i]-l[i-1])
for i in range(1,n-1):
if l[i]>l[i-1] and l[i]>l[i+1]:
ans-=l[i]-max(l[i-1],l[i+1])
if l[0]>l[1]:
ans-=l[0]-l[1]
if l[-1]>l[-2]:
ans-=l[-1]-l[-2]
print(ans)
t-=1#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7;
const int INF_INT = 0x3f3f3f3f;
const long double PI = acosl(-1.), EPS = 1e-9;
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> v(n);
ll curug = 0;
for(int i=0;i<n;i++){
cin >> v[i];
if(i == 0) curug += v[i];
else curug += abs(v[i] - v[i-1]);
}
curug += v[n-1];
if(n == 1){
cout << curug/2 << "\n";
return;
}
if(n >=2 && v[0] > v[1]) {
curug -= v[0] - v[1];
v[0] = v[1];
}
for(int i=1;i<(n-1);i++){
if(v[i] > v[i-1] && v[i] > v[i+1]){
curug -= v[i] - max(v[i-1], v[i+1]);
v[i] = max(v[i-1], v[i+1]);
}
}
if(n >= 2) curug -= max(v[n-1] - v[n-2], 0);
cout << curug << "\n";
}
//cout << fixed << setprecision(6)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("in", "r", stdin); test input
int t;
cin >> t;
while(t--){
solve();
}
}
807A - Is it rated | 1096A - Find Divisible |
1430C - Numbers on Whiteboard | 1697B - Promo |
208D - Prizes Prizes more Prizes | 659A - Round House |
1492C - Maximum width | 171B - Star |
1512B - Almost Rectangle | 831B - Keyboard Layouts |
814A - An abandoned sentiment from past | 268C - Beautiful Sets of Points |
1391C - Cyclic Permutations | 11A - Increasing Sequence |
1406A - Subset Mex | 1365F - Swaps Again |
50B - Choosing Symbol Pairs | 1719A - Chip Game |
454B - Little Pony and Sort by Shift | 1152A - Neko Finds Grapes |
1719B - Mathematical Circus | 1719C - Fighting Tournament |
1642A - Hard Way | 285C - Building Permutation |
1719E - Fibonacci Strings | 1696C - Fishingprince Plays With Array |
1085A - Right-Left Cipher | 1508B - Almost Sorted |
1690C - Restoring the Duration of Tasks | 1055A - Metro |