#pragma GCC optimize("O3") #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long; using P = pair<int, int>; using T = tuple<int, int, int>; template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;} template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;} constexpr int MOD = 1e9 + 7; constexpr int inf = 1e9; constexpr long long INF = 1e18; #define all(a) (a).begin(), (a).end() int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(){ cin.tie(0); ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++) cin>>a[i]; vector<vector<int>> aa(3, vector<int>(n)); for(int i=0; i<3; i++){ for(int j=0; j<n; j++){ aa[i][j] = a[(i + j) % n]; } } ll ans = 0; for(int i=0; i<3; i++){ vector<ll> dp(n + 1, 0); for(int j=0; j<n; j++){ chmax(dp[j + 1], dp[j]); int idx1 = j, idx2 = (j + 1) % n, idx3 = (j + 2) % n; if(aa[i][idx1] == aa[i][idx2] || aa[i][idx1] == aa[i][idx3] || aa[i][idx2] == aa[i][idx3]) continue; if(!((aa[i][idx1] < aa[i][idx2] && aa[i][idx2] > aa[i][idx3]) || (aa[i][idx1] > aa[i][idx2] && aa[i][idx2] < aa[i][idx3]))) continue; if(j + 3 <= n) chmax(dp[j + 3], dp[j] + aa[i][idx1]); } chmax(ans, dp[n]); } cout << ans << endl; } return 0; }