1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <vector>
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
using namespace std;

int z, n;
int first_pos, last_pos;
bool error;

int main() {
    scanf("%d", &z);
    while(z--) {
        scanf("%d", &n);
        vector<int> A(n);
        FOR(i,0,n) scanf("%d", &A[i]);

        // Rule 1 - no gaps inside
        first_pos = -1;
        last_pos = -1;
        FOR(i,0,n) {
            if (A[i] != 0) {
                if (first_pos == -1) first_pos = i;
                last_pos = i;
            }
        }
        error = false;
        FOR(i,first_pos,last_pos+1) {
            if (A[i] == 0) {
                error = true;
                break;
            }
        }
        if (error) { printf("NIE\n"); continue; }

        // Rule 2 - length 1
        if (first_pos == last_pos) {
            if (A[first_pos] == 1) printf("TAK\n"); else printf("NIE\n");
            continue;
        }

        // Rule 3 - odd and even sum should be in [-1, 0, 1]
        signed long long int S = 0;
        FOR(i,first_pos,last_pos+1) if (i&1) S += A[i]; else S -= A[i];
        if (S != -1 && S != 0 && S != 1) { printf("NIE\n"); continue; }

        // Rule 4 - No regress at the beginning and end
        if (last_pos - first_pos + 1 > 2) {
            if (A[first_pos] > A[first_pos+1]) { printf("NIE\n"); continue; }
            if (A[last_pos] > A[last_pos-1]) { printf("NIE\n"); continue; }
        }

        // Rule 5 - no "hop" inside
        if (last_pos - first_pos + 1 > 3) {
            error = false;
            FOR(i,first_pos+1, last_pos) {
                if (A[i] > A[i-1] + A[i+1]) {
                    error = true;
                    break;
                }
            }
            if (error) { printf("NIE\n"); continue; }
        }

        // Rule 6a - cut from left
        error = false;
        while (last_pos - first_pos + 1 > 2) {
            if (A[first_pos] == A[first_pos+1]) {
                A[first_pos+1] = 1;
                A[first_pos] = 1;
                break;
            } else if (A[first_pos] < A[first_pos+1]) {
                A[first_pos+1] -= A[first_pos];
                A[first_pos] = 0;
                ++first_pos;
            } else {
                error = true;
                break;
            }
        }
        if (error) { printf("NIE\n"); continue; }

        // Rule 6b - cut from right
        error = false;
        while (last_pos - first_pos + 1 > 2) {
            if (A[last_pos] == A[last_pos-1]) {
                A[last_pos-1] = 1;
                A[last_pos] = 1;
                break;
            } else if (A[last_pos] < A[last_pos-1]) {
                A[last_pos-1] -= A[last_pos];
                A[last_pos] = 0;
                --last_pos;
            } else {
                error = true;
                break;
            }
        }
        if (error) { printf("NIE\n"); continue; }

        // Rule 6c
        if (last_pos - first_pos + 1 == 2) {
            int diff = A[first_pos] - A[last_pos];
            if (diff == -1 || diff == 0 || diff == 1) printf("TAK\n"); else printf("NIE\n");
            continue;
        }

        // Rule 6d
        if (last_pos - first_pos + 1 <= 4) {
            error = false;
            FOR(i,first_pos,last_pos+1) if (A[i] != 1) { error = true; break; }
            if (error) printf("NIE\n"); else printf("TAK\n");
            continue;
        }

        // Rule 7 - check if A can be ZIG-ZAG
        first_pos += 2;
        last_pos -= 2;
        error = false;
        FOR(i,first_pos,last_pos) {
            if (A[i+1] <= A[i]-1) { error = true; break; }
            A[i+1] = A[i+1] - A[i] + 1;
            A[i] = 0;
            ++first_pos;
        }
        if (error || A[last_pos] != 1) { printf("NIE\n"); continue; }

        printf("TAK\n");
    }
}