/* -*- coding: utf-8 -*- * * 1368.cc: No.1368 サイクルの中に眠る門松列 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200000; /* typedef */ typedef long long ll; /* global variables */ int as[MAX_N + 2]; ll dp[MAX_N + 1]; /* subroutines */ bool kadomatsu(int v[]) { return v[0] != v[2] && ((v[0] < v[1] && v[1] > v[2]) || (v[0] > v[1] && v[1] < v[2])); } inline void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int tn; scanf("%d", &tn); while (tn--) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", as + i); as[n] = as[0], as[n + 1] = as[1]; ll maxsum = 0; for (int st = 0; st < 3; st++) { fill(dp, dp + n + 1, 0); for (int i = 0, j = st; i < n; i++, j++) { setmax(dp[i + 1], dp[i]); if (i + 3 <= n && kadomatsu(as + j)) setmax(dp[i + 3], dp[i] + as[j]); } setmax(maxsum, dp[n]); } printf("%lld\n", maxsum); } return 0; }