Binary Search
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
void solve() {
int n;
cin >> n;
vector<int> pos(n), neg(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (x == 1) pos[i] += 1;
else if (x == -1) neg[i] += 1;
if (i > 0) {
pos[i] += pos[i - 1];
neg[i] += neg[i - 1];
}
}
auto get = [&] (int l, int r, vector<int> &x) {
return x[r] - (l ? x[l - 1] : 0);
};
auto check = [&] (int l, int r) {
assert(l <= r && r < n);
return get(l, r, pos) <= 1 && get(l, r, neg) <= 1;
};
ll ans = 0;
for (int i = 0; i < n - 1; ++i) {
int l = 2, r = n - i, best = 1;
while (l <= r) {
int m = (l + r) / 2;
if (check(i, i + m - 1)) {
l = m + 1;
best = m;
} else r = m - 1;
}
ans += best - 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}