t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
pos = [0 for i in range(n+1)]
neg = [0 for j in range(n+1)]
for i in range(n):
if a[i] > 0:
if pos[i] > 0:
if a[i] == 1:
pos[i+1] = pos[i]
else:
pos[i+1] = pos[i] + 1
else:
if a[i] == 1:
pos[i+1] = 1
else:
pos[i+1] = 2
if neg[i] < 0:
if a[i] == 1:
neg[i+1] = neg[i]
else:
neg[i+1] = neg[i] - 1
elif a[i] < 0:
if neg[i] == 0:
pos[i+1] = 0
else:
if a[i] == -1:
pos[i+1] = abs(neg[i])
else:
pos[i+1] = abs(neg[i]) + 1
if pos[i] == 0:
neg[i+1] = a[i]
else:
if a[i] == -1:
neg[i+1] = -pos[i]
else:
neg[i+1] = -(pos[i] + 1)
best = 1
best_index = -1
for i in range(1, n+1):
if pos[i] > best:
best = pos[i]
best_index = i
if best == 1 or best_index == -1:
print(n, 0)
else:
last_part = n - best_index
sign = 0 twos_required = best - 1
twos_seen = 0
for i in range(best_index, 0, -1):
if abs(a[i-1]) == 2:
twos_seen += 1
if a[i-1] < 0:
if sign == 1:
sign = 0
else:
sign = 1
if twos_seen == twos_required and sign == 0:
first_part = i
break
print(first_part - 1, last_part)
#include <bits/stdc++.h>
#define IN cin
#define OUT cout
using namespace std;
#define FOR(a,b,c) for(int a=b; a < c; a++)
int T;
int N;
vector<int> A;
vector<int> C2;
int FindNextNonZero(int pos)
{
FOR(i,pos,N)
{
assert(i >= 0 && i < N);
if(A[i] != 0)
return i;
}
return -1;
}
int FindNextZero(int pos)
{
FOR(i,pos,N)
{
assert(i >= 0 && i < N);
if(A[i] == 0)
return i;
}
return -1;
}
pair<int, pair<int, int>> comp(int lower, int upper)
{
if(lower == upper)
{
if(A[lower] == 2)
return {1, {lower, N-1-lower}};
else
return {0,{-1,-1}};
}
assert(lower >= 0 && upper < N && lower <= upper);
int neg_count = 0;
int first_neg = -1;
int last_neg = -1;
for(int i = lower; i <= upper; i++)
{
assert(i >= 0 && i < N);
if(A[i] < 0)
{
neg_count++;
last_neg = i;
}
}
for(int i=lower; i <= upper; i++)
{
assert(i >= 0 && i < N);
if(A[i] < 0)
{
first_neg = i;
break;
}
}
if(neg_count % 2 == 0)
{
int prod;
if(lower > 0)
prod = C2[upper] - C2[lower-1];
else
prod = C2[upper];
return {prod, {lower, N-upper-1}};
}
int left_prod = 0;
if(lower > 0 && last_neg > 0)
left_prod = C2[last_neg-1] - C2[lower -1];
else if(last_neg > 0)
left_prod = C2[last_neg-1];
int right_prod = C2[upper] - C2[first_neg];
if(right_prod > left_prod)
{
return {right_prod,{first_neg + 1, N-upper-1}};
}
return {left_prod,{lower, N-last_neg}};
}
pair<int, int> solve()
{
A = vector<int>(N);
C2 = vector<int>(N);
FOR(n,0,N)
{
IN >> A[n];
if(n == 0)
{
C2[0] = (A[n] == -2 || A[n] == 2);
} else
{
C2[n] = C2[n-1] + (A[n] == -2 || A[n] == 2);
}
}
int first_nonzero = FindNextNonZero(0);
if(first_nonzero == -1)
return {N, 0};
int index = first_nonzero;
vector<pair<int, int>> Q;
while(index < N)
{
int next_zero = FindNextZero(index);
if(next_zero == -1)
{
Q.push_back({index, N-1});
break;
} else
{
Q.push_back({index, next_zero -1});
}
index = FindNextNonZero(next_zero + 1);
if(index == -1)
break;
}
int prod = 0;
pair<int, int> ans = {N,0};
for(auto [l, u] : Q)
{
auto [a, p] = comp(l,u);
if(a > prod)
{
ans = p;
prod = a;
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
////////////////////////
////////////////////////
IN >> T;
FOR(t,0,T)
{
IN >> N;
auto [x,y] = solve();
OUT << x << " " << y << "\n";
}
OUT << flush;
}
1114A - Got Any Grapes | 224B - Array |
125B - Simple XML | 567B - Berland National Library |
431B - Shower Line | 282C - XOR and OR |
1582B - Luntik and Subsequences | 609A - Флеш-карты |
1207A - There Are Two Types Of Burgers | 371C - Hamburgers |
343B - Alternating Current | 758B - Blown Garland |
1681B - Card Trick | 1592A - Gamer Hemose |
493D - Vasya and Chess | 1485A - Add and Divide |
337B - Routine Problem | 1392D - Omkar and Bed Wars |
76E - Points | 762C - Two strings |
802M - April Fools' Problem (easy) | 577B - Modulo Sum |
1555B - Two Tables | 1686A - Everything Everywhere All But One |
1469B - Red and Blue | 1257B - Magic Stick |
18C - Stripe | 1203B - Equal Rectangles |
1536A - Omkar and Bad Story | 1509A - Average Height |