#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n;
int a[N];
int Left[N][N], Right[N][N];

int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int len = 1; len <= n; len++)
            for(int l = 1; l + len - 1 <= n; l++){
                int r = l + len - 1;
                if(l == r) Left[l][r] = Right[l][r] = a[l];
                else{
                    int L = Left[l][r - 1], R = Right[l][r - 1], X = a[r];
                    int &yl = Left[l][r];
                    if(X == R) yl = 0;
                    else if(X < R && X <= L || R < X && L <= X) yl = X;
                    else if(L < R) yl = X + 1;
                    else yl = X - 1;

                    L = Left[l + 1][r], R = Right[l + 1][r], X = a[l];
                    int &yr = Right[l][r];
                    if(X == L) yr = 0;
                    else if(X <= R && X < L || R <= X && L < X) yr = X;
                    else if(L > R) yr = X + 1;
                    else yr = X - 1;
                }
            }
        if(n == 1) cout << 1 << endl;
        else printf("%d\n", a[1] != Left[2][n]);
    }
}

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 55, M = N * 1000;

int n;
int f[N][M];

bool dfs(int a, int b){
    int &v = f[a][b];
    if(v != -1) return v;
    if(b == 1) return dfs(a + 1, 0);
    if(!a) return v = b & 1;

    if(a && !dfs(a - 1, b)) return v = 1;
    if(b && !dfs(a, b - 1)) return v = 1;
    if(a >= 2 && !dfs(a - 2, b + (b ? 3 : 2))) return v = 1;
    if(a && b && !dfs(a - 1, b + 1)) return v = 1;

    return v = 0;
}
int main(){
    int T;
    cin >> T;
    memset(f, -1, sizeof f);
    while(T--){
        cin >> n;
        int a = 0, b = 0;
        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
            if(x == 1) a++;
            else b += x;
        }
        b += n - a - 1;
        if(dfs(a, b)) puts("YES");
        else puts("NO");
    }
}

#include<iostream>
#include<cmath>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int f[N][20];

void init(){
    for(int j = 1; j < 18; j++)
        for(int i = 1; i + (1 << j) <= n + 1; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r){
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> f[i][0];
    init();
    cin >> m;
    while(m--){
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
using namespace std;

const int N = 1e6;
long long a[N], tmp[N];
long long mergesort(int l,int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    long long cnt = mergesort(l, mid) + mergesort(mid + 1, r);
    int st1 = l, st2 = mid + 1;
    for (int i = l; i <= r; i++) {
        if (st1 <= mid && a[st1] < a[st2] || st2 > r)
            tmp[i] = a[st1++];
        else {
            tmp[i] = a[st2++];
            cnt += mid - st1 + 1;
        }
    }
    for (int i = l; i <= r; i++) 
        a[i] = tmp[i];
    return cnt;
}
int main() {
    int n;
    while (cin >> n, n) {
        for (int i = 0; i < n; i++)
            cin >> a[i];
        cout << mergesort(0, n - 1) << endl;
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
using namespace std;

const int N = 1e5 + 4;

priority_queue<int> a;
priority_queue<int, vector<int>, greater<int>> b;

void ins(int x) {
    b.push(x);
    if (b.size() > a.size()) {
        a.push(b.top());
        b.pop();
    }
    while (a.size() && b.size() && a.top() > b.top()) {
        b.push(a.top());
        a.pop();
        a.push(b.top());
        b.pop();
    }
}
int getmid() {
    return a.top();
}
int p[N];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, m;
        cin >> x >> m;
        for (int i = 1; i <= m; i++) 
            cin >> p[i];

        cout << x << ' ' << (m + 1) / 2 << endl;
        int k = 0;
        for (int i = 1; i <= m; i++) {
            k++;
            ins(p[i]);
            if (i & 1) cout << getmid() << ' ';
            if (k % 20 == 0) cout << endl;
        }
        if (k % 20) cout << endl;
        while (a.size()) a.pop();
        while (b.size()) b.pop();
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, m, T;
int col[N], row[N];
int sum[N];
LL make(int n, int p[]){
    if(T % n) return -1;
    int ave = T / n;
    LL res = 0;
    for(int i = 1; i <= n; i++) p[i] -= ave;
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + p[i];

    sort(sum + 1, sum + n + 1);
    int mid = 1 + n >> 1;
    for(int i = 1; i <= n; i++) res += abs(sum[mid] - sum[i]);
    return res;
}
int main(){
    cin >> n >> m >> T;
    for(int i = 0; i < T; i++){
        int x, y;
        cin >> x >> y;
        row[x]++;
        col[y]++;
    }
    LL ans1 = make(n, row), ans2 = make(m, col);
    if(ans1 != -1 && ans2 != -1) printf("both %lld\n", ans1 + ans2);
    else if(ans2 != -1) printf("column %lld\n", ans2);
    else if(ans1 != -1) printf("row %lld\n", ans1);
    else puts("impossible");
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 2010, M = 6010;

int n, m, k;
int h[N], e[M], ne[M], idx;
int sg[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u){
    if(sg[u] != -1) return sg[u];

    unordered_set<int> map;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        map.insert(dfs(j));
    }
    for(int i = 0;; i++)
        if(!map.count(i)) return sg[u] = i;
}
int main(){
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    memset(sg, -1, sizeof sg);
    while(m--){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 0; i < k; i++){
        int x;
        cin >> x;
        res ^= dfs(x);
    }
    if(res) puts("win");
    else puts("lose");
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
using namespace std;

typedef long long LL;
pair<LL, LL> trans(LL z,int n) {
    LL x, y;
    if (n == 1) {
        if (z == 1) x = 1, y = 1;
        if (z == 2) x = 1, y = 2;
        if (z == 3) x = 2, y = 2;
        if (z == 4) x = 2, y = 1;
        return pair<LL, LL>(x, y);
    }
    LL len = 1LL << (n - 1);
    LL lenn = 1LL << 2 * n - 2;
    int k = z - 1 >> 2 * n - 2;
    auto p = trans((z - 1) % lenn + 1, n - 1);
    switch (k){
    case 0:
        x = p.second;
        y = p.first;
        break;
    case 1:
        x = p.first;
        y = p.second + len;
        break;
    case 2:
        x = p.first + len;
        y = p.second +len;
        break;
    case 3:
        x = 2*len - p.second + 1;
        y = len - p.first + 1;
        break;
    default:
        break;
    }
    return pair<LL, LL>(x, y);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        LL n, a, b;
        cin >> n >> a >> b;
        auto A = trans(a, n);
        auto B = trans(b, n);
        LL dx = A.first - B.first;
        LL dy = A.second - B.second;
        double k = sqrt((dx * dx + dy * dy)) * 10;
        printf("%.0lf\n", k);
    }
    return 0;
}

#include<iostream> 
#include<algorithm>

using namespace std;

const int N = 5e3 + 10;
int s[N][N];

int main(){
    int n, r;
    cin >> n >> r;
    int down = 0, right = 0;
    for(int i = 0; i < n; i++){
        int x, y, w;
        cin >> x >> y >> w;
        s[++x][++y] += w;
        if(x > down) down = x;
        if(y > right) right = y;
    }
    for(int i = 1; i <= down; i++)
        for(int j = 1; j <= right; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    int res = 0;
    for(int i = 1; i <= down; i++)
        for(int j = 1; j <= right; j++){
            int x1 = max(0, i - r);
            int y1 = max(0, j - r);
            res = max(res, s[i][j] - s[i][y1] - s[x1][j] + s[x1][y1]);
        }

    cout << res << endl;
    return 0;
}