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
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr int maxn = 1e6 + 7;
int z, n, res, poz, larm, minx, a, b, res2;
int t[maxn], t2[maxn];


int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> z;
    // cerr << z << '\n';
    while(z--){
        poz = 0;
        cin >> n;
        larm = 0;
        res = 1;
        for(int i = 1; i <= n + 5; i++) t[i] = t2[i] = 0;
        for(int i = 1; i <= n; i++){
            cin >> t[i];
            if(t[i] != 0 && poz == 0) poz = i;
            t2[i] = t[i];
        }
        for(int i = 1; i <= n; i++){
            if(t[i] == 0 && i > poz && larm == 0){
                larm = i;
            }
            if(larm > 0 && t[i] > 0){
                res = 0;
            }
        }
        if(res == 0){
            cout << "NIE\n";
            continue;
        }
        res = 1;
        // t[poz] = max(0LL, t[poz] - 1LL);
        for(int i = 2; i <= n + 1; i++){
            a = t[i - 1];
            b = t[i];
            a = max(0LL, a - 1);
            minx = min(a, b);
            a -= minx;
            b -= minx;
            t[i - 1] = a;
            t[i] = b;
            // cout << a << " " << b << '\n';
            if(a == 0) continue;
            else res = 0;
            if(res == 0) break;
        }
        //////////////////////////
        res2 = 1;
        t2[poz + 1] = max(0LL, t2[poz + 1] - 1);
        // t2[poz] = max(0LL, t2[poz] - 1);
        for(int i = 2; i <= n + 1; i++){
            a = t2[i - 1];
            b = t2[i];
            a = max(0LL, a - 1);
            minx = min(a, b);
            a -= minx;
            b -= minx;
            t2[i - 1] = a;
            t2[i] = b;
            // cout << a << " " << b << '\n';
            if(a <= 0) continue;
            else res2 = 0;
            if(res2 == 0) break;
        }
        // if(t[n] > 0) res = 0;
        if((res | res2) == 1) cout << "TAK\n";
        else cout << "NIE\n";
    }
}