#include #include #include #include #include #include #include #include #include #include #include #include #include //#include #define Size 1000005 #define inf 2e9 #define INF 2e18 #define LL long long int #define i64 __int64 #define ULL unsigned long long #define Mod 1000000007 #define pi 4*atan(1) #define eps 1e-8 #define lson now*2,l,l+(r-l)/2 #define rson now*2+1,l+(r-l)/2+1,r #define Max(a,b) (a)>(b)?(a):(b) using namespace std; int n,m,k; int ql,qr,pos; int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ONLINE_JUDGE int t; int x,y,z; srand(time(NULL)); int Case=0; cin>>t; while(t--) // while(scanf("%d",&n)==1) { // printf("Case #%d: ",++Case); scanf("%d",&n); int flag1 = 0,flag2 = 0; int tmp; for(int i=0;i