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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin>>t;
    while (t--) {
        int n;
        cin>>n;
        vector<int> as(n);
        for (int i=0; i<n; i++) cin>>as[i];
        bool good = true;
        bool start_right=false, start_left=false;
        int ir=n-1,il=0;

        while (ir>0 && as[ir]==0) ir--;
        while (il<n-1 && as[il]==0) il++;

        for (int i=il; i<=ir; i++) if (as[i] == 0) {
            good = false;
            break;
        }

        while (ir!=il && good) {

            if (as[ir] < as[ir-1]) {
                as[ir-1] -= as[ir]+start_right;
                ir--;
                continue;
            }

            if (as[il] < as[il+1]) {
                as[il+1] -= as[il]+start_left;
                il++;
                continue;
            }

            if (!start_left && !start_right) {
                if (il+1 == ir) {
                    if (as[il]+1 == as[ir]) {
                        as[il+1]=0;
                        il++;
                        continue;
                    }

                    if (as[il] == as[ir]+1) {
                        as[ir-1]=0;
                        ir--;
                        continue;
                    }
                }

                if (as[ir] == as[ir-1]) {
                    as[ir-1] = 0;
                    ir--;
                    start_right = true;
                    continue;
                }

                if (as[il] == as[il+1]) {
                    as[il+1] = 0;
                    il++;
                    start_left = true;
                    continue;
                }
            }

            if (il+1 == ir) {
                if (as[il] == as[ir]) {
                    as[il+1]=0;
                    il++;
                    continue;
                }

                if (as[il] == as[ir]) {
                    as[ir-1]=0;
                    ir--;
                    continue;
                }
            }

            good = false;
        }

        if (as[ir]>1 || (as[ir]>0 && (start_left || start_right))) good = false;

        if (good) cout<<"TAK\n";
        else cout<<"NIE\n";
    }

    return 0;
}