#include<bits/stdc++.h> using namespace std; #define ll long long ll a[500010],dp[500010][2]; void solve(){ ll n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i][0]=dp[i][1]=0; //dp[i][0]表示第i个点作为区间终点 //dp[i][1]表示第i个点作为区间起点 } if(n1){ cout<<0<<endl; return; } bool flag=0;//默认递增 int last=1;//上一个顶点 for(int i=1;i<n;i++){ if(i1){ if(a[i]>a[i+1]) flag=0; else flag=1; } //如果是顶点，那么转移。 if(flag0&&a[i]<a[i+1]){ dp[i][0]=max(dp[last][0]+abs(a[i]-a[last+1]),dp[last][1]+abs(a[i]-a[last])); dp[i][1]=dp[last][1]+abs(a[i-1]-a[last]); if(i!=last+1){ dp[i][1]=max(dp[i][1],dp[last][0]+abs(a[i-1]-a[last+1])); } else dp[i][1]=max(dp[i][1],dp[last][0]); flag=1;last=i; } if(flag1&&a[i]>a[i+1]){ dp[i][0]=max(dp[last][0]+abs(a[i]-a[last+1]),dp[last][1]+abs(a[i]-a[last])); dp[i][1]=dp[last][1]+abs(a[i-1]-a[last]); if(i!=last+1){ dp[i][1]=max(dp[i][1],dp[last][0]+abs(a[i-1]-a[last+1])); } else dp[i][1]=max(dp[i][1],dp[last][0]); flag=0;last=i; } } cout<<max(dp[last][0]+abs(a[n]-a[last+1]),dp[last][1]+abs(a[n]-a[last]))<<endl; //答案：第n个点作为区间终点的权值和 } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }