#include #include #include using namespace std; using ll = long long; ll kado(int a , int b , int c){ if(a == b || b == c || c == a){ return 0; } if(b < a && b < c){ return a; } if(b > a && b > c){ return a; } return 0; } void solve(){ int n; cin >> n; vector a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } a.push_back(a[0]); a.push_back(a[1]); vector KadoTable(n + 2 , 0); KadoTable[0] = 0; KadoTable[1] = 0; for(int i = 2; i < n + 2; i++){ KadoTable[i] = kado(a[i - 2] , a[i - 1] , a[i]); } vector dp(n + 2 , 0); dp[0] = KadoTable[0]; dp[1] = KadoTable[1]; dp[2] = KadoTable[2]; for(int i = 3; i < n + 2; i++){ dp[i] = max(KadoTable[i] + KadoTable[i - 3] , KadoTable[i - 1]); } cout << dp[n + 1] << endl; } int main() { int t; cin >> t; for(int i = 0; i < t; i++)solve(); return 0; }