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>

#define ll long long

using namespace std;

const int N = 1000007;

ll tab[N], L[N], R[N], Lxd[N], Rxd[N];

string zad (int n) {
    L[0] = tab[0];
    Lxd[0] = tab[0];
    for (int i = 1; i < n; ++i) {
        L[i] = tab[i] - L[i-1] + 1;
        if (L[i] <= 0 && i < n-1) return "NIE";
        Lxd[i] = tab[i] - Lxd[i-1];
    }
    // for (int i = 0; i < n; ++i) {
    //     cout<<L[i]<<' ';
    // }
    // cout<<'\n';
    // for (int i = 0; i < n; ++i) {
    //     cout<<Lxd[i]<<' ';
    // }
    // cout<<'\n';
    R[n-1] = tab[n-1];
    Rxd[n-1] = tab[n-1];
    for (int i = n-2; i >= 0; --i) {
        R[i] = tab[i] - R[i+1] + 1;
        if (R[i] <= 0 && i > 0) return "NIE";
        Rxd[i] = tab[i] - Rxd[i+1];
    }
    // for (int i = 0; i < n; ++i) {
    //     cout<<R[i]<<' ';
    // }
    // cout<<'\n';
    // for (int i = 0; i < n; ++i) {
    //     cout<<Rxd[i]<<' ';
    // }
    // cout<<'\n';
    if (L[n-1] == 1 || R[0] == 1 || L[n-1] == 0 || R[0] == 0) return "TAK";
    
    for (int i = 0; i < n; ++i) {
        if (tab[i] - Lxd[i] == Rxd[i+1]) return "TAK";
        if (i < n-1 && Lxd[i] == R[i+1]) return "TAK";
        if (i > 0 && L[i-1] == Rxd[i]) return "TAK";
    }

    return "NIE";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t, n;
    cin>>t;
    for (int i = 0; i < t; ++i) {
        cin>>n;
        int id = 0;
        ll a;
        bool ended = false, started = false, fail = false;
        for (int j = 0; j < n; ++j) {
            cin>>a;
            if (a != 0) {
                if (ended) fail = true;
                started = true;
                tab[id++] = a;
            } else {
                if (started) ended = true;
            }
        }
        if (fail) cout<<"NIE\n";
        else if (id == 0) cout<<"TAK\n";
        else cout<<zad(id)<<'\n';
    }
}