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
#include <iostream>
#include <algorithm>

// #define debug

const int MAX = 1000000+2;

int64_t M[MAX];
int64_t B[MAX];

struct node {
    int64_t in, out;
};

node D[MAX];

bool solve() {
    int n;
    std::cin >> n;
    for (int i=0;i<n;++i) std::cin >> M[i];
    for (int i=0;i<n;++i) {
        D[i] = {0,0};
        B[i] = 0;
    }
    M[n] = 1000000009;

    int il = 0;
    int ir = n-1;
    while (M[il] == 0) ++il;
    while (M[ir] == 0) --ir;

    int64_t l = M[il];
    int64_t r = M[il];
    bool borrow = false;
    bool borrow_cap = false;
    for (int i=il+1;i<=ir;++i) {


        if (M[i] == 0) return false;
        if (r == 0) {
            // if (borrow || !borrow_cap) {
            //     // std::clog << "borrow || !borrow_cap" << std::endl;
            //     return false;
            // }
            // if (D[i-2])
            // D[i-2].in--;
            // D[i-1].out--;
            B[i]++;
            ++r;
            borrow = true;
        }
        // if (!borrow && r >1) borrow_cap = true;
        #ifdef debug
        std::clog << " :: " << M[i] << " " << l << " / " << r << std::endl;
        #endif

        
        D[i-1].out += r;
        D[i-1].in += l;
        
        D[i].out += l;
        D[i].in += r;
        #ifdef debug
        std::clog << " :: :: A " << M[i] << " | " << D[i-1].out << " / " << D[i-1].in << std::endl;
        std::clog << " :: :: B " << M[i] << " | " << D[i].out << " / " << D[i].in << std::endl;
        #endif
        
        r = std::min(M[i] - D[i].out, M[i+1]);
        l = std::min(M[i] - D[i].in, M[i+1]);
    }

    int64_t bb = 0;
    for (int i=ir;i>il;--i) {
        bb += B[i];
        if (bb > 0 && D[i-2].in > 1 && D[i-1].out > 1) {
            D[i-2].in--;
            D[i-1].out--;
            --bb;
        }
    }

    int bad_in = 0;
    int bad_out = 0;
    for (int i=il;i<=ir;++i) {

        #ifdef debug
        std::clog << M[i] << " (" << D[i].in << ", " << D[i].out << " || " << B[i] << ")" << std::endl;
        #endif

        if (D[i].in == M[i]) {
            // OK
        } else if (D[i].in+1 == M[i]) {
            ++bad_in;
        } else {
            #ifdef debug
            std::clog << "bad_in" << std::endl;
            #endif
            bad_in+=2;
        }
        if (D[i].out == M[i]) {
            // OK
        } else if (D[i].out+1 == M[i]) {
            ++bad_out;
        } else {
            #ifdef debug
            std::clog << "bad_out" << std::endl;
            #endif
            bad_out+=2;
        }
    }

    return bad_in == 0 && bad_out == 0 || bad_in == 1 && bad_out == 1;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    int t;
    std::cin >> t;
    while (t--) std::cout << (solve() ? "TAK" : "NIE") << "\n";
    return 0;
}