#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define endl codeforces #define ALL(v) std::begin(v), std::end(v) #define ALLR(v) std::rbegin(v), std::rend(v) using ll = std::int64_t; using ull = std::uint64_t; using pii = std::pair; using tii = std::tuple; using pll = std::pair; using tll = std::tuple; using size_type = ssize_t; template using vec = std::vector; template using vvec = vec>; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template struct multi_dim_array { using type = std::array::type, Head>; }; template struct multi_dim_array { using type = std::array; }; template using mdarray = typename multi_dim_array::type; template void fill_seq(T &t, F f, Args... args) { if constexpr (std::is_invocable::value) { t = f(args...); } else { for (size_type i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i); } } template vec make_v(size_type sz) { return vec(sz); } template auto make_v(size_type hs, Tail&&... ts) { auto v = std::move(make_v(std::forward(ts)...)); return vec(hs, v); } namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; } template T ceil_pow2(T bound) { T ret = 1; while (ret < bound) ret *= 2; return ret; } template T ceil_div(T a, T b) { return a / b + !!(a % b); } const ll SIZE = 2e5 + 10; mdarray dp; const ll inf = 5e15; ll solve(const std::vector &av) { const ll n = av.size(); auto check = [&](ll idx) { std::array c = {{ av[idx], av[(idx + 1) % n], av[(idx + 2) % n] }}; if (c[0] == c[1] || c[1] == c[2] || c[2] == c[0]) return false; if (c[0] < c[1] && c[2] < c[1]) return true; if (c[1] < c[0] && c[1] < c[2]) return true; return false; }; for (ll i = 0; i <= n; i++) for (ll j = 0; j < 3; j++) dp[i][j] = 0; if (check(0)) chmax(dp[3][0], av[0]); if (check(1)) chmax(dp[std::min(4, n)][1], av[1]); for (ll i = 2; i < n; i++) { const bool ok = check(i); for (ll j = 0; j < 3; j++) { chmax(dp[i + 1][j], dp[i][j]); if (ok) { if (i < n - 2) { chmax(dp[i + 3][j], av[i] + dp[i][j]); } else if (i == n - 2 && j < 2) { chmax(dp[n][j], av[i] + dp[i][j]); } else if (i == n - 1 && j == 2) { chmax(dp[n][j], av[i] + dp[i][j]); } } } } return *std::max_element(ALL(dp[n])); } int main() { ll t; std::cin >> t; while (t--) { ll n; std::cin >> n; vec av(n); for (ll &e : av) std::cin >> e; std::cout << solve(av) << "\n"; } return 0; }