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
130
131
132
133
134
135
136
137
138
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector <ll> v(n);
        for (auto &x : v)
            cin >> x;
        while (v.back() == 0) v.pop_back();
        reverse(v.begin(), v.end());
        while (v.back() == 0) v.pop_back();

        n = v.size();
        if (n == 1) {
            cout << (v[0] == 1 ? "TAK\n" : "NIE\n");
            continue;
        }

        bool zero = false;
        for (auto x : v) if (x == 0) {
            zero = true;
            break;
        }
        if (zero) {
            cout << "NIE\n";
            continue;
        }

        vector <int> start;
        bool good = true;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                if (v[0] - 1 == v[1]) start.push_back(0);
                else if (v[0] - 1 > v[1]) good = false;
            } else if (i == n - 1) {
                if (v[n - 1] - 1 == v[n - 2]) start.push_back(n - 1);
                else if (v[n - 1] - 1 > v[n - 2]) good = false;
            } else {
                if (v[i - 1] + v[i + 1] == v[i] - 1) start.push_back(i);
                else if (v[i - 1] + v[i + 1] < v[i] - 1) good = false;
            }
        }

        if (!good || start.size() >= 2) {
            cout << "NIE\n";
            continue;
        } else if (start.size() == 0) {
            vector <ll> in(n), out(n);
            for (int i = 0; i < n; i++) {
                in[i] = v[i];
                out[i] = v[i];
            }
            int l = 0, r = n - 1, m = 0;
            while (l < r) {
                if (in[l] < out[l + 1]) {
                    out[l + 1] -= in[l];
                    in[l + 1] -= out[l];
                    in[l] = 0;
                    out[l] = 0;
                    l++;
                } else if (in[r] < out[r - 1]) {
                    out[r - 1] -= in[r];
                    in[r - 1] -= out[r];
                    in[r] = 0;
                    out[r] = 0;
                    r--;
                } else if (m && in[l] == out[l + 1]) {
                    in[l]--;
                    m = 0;
                } else if (m && in[r] == out[r + 1]) {
                    in[r]--;
                    m = 0;
                } else break;
            }
            ll cnt_in = 0, cnt_out = 0;
            for (int i = 0; i < n; i++) {
                cnt_in += in[i];
                cnt_out += out[i];
            }
            if ((m == 0 && cnt_in == 0 && cnt_out == 1) || (m == 1 && cnt_in == cnt_out && cnt_in <= 1)) {
                cout << "TAK\n";
                continue;
            }

            reverse(v.begin(), v.end());
            for (int i = 0; i < n; i++) {
                in[i] = v[i];
                out[i] = v[i];
            }
            l = 0, r = n - 1, m = 1;
            while (l < r) {
                if (in[l] < out[l + 1]) {
                    out[l + 1] -= in[l];
                    in[l + 1] -= out[l];
                    in[l] = 0;
                    out[l] = 0;
                    l++;
                } else if (in[r] < out[r - 1]) {
                    out[r - 1] -= in[r];
                    in[r - 1] -= out[r];
                    in[r] = 0;
                    out[r] = 0;
                    r--;
                } else if (m && in[l] == out[l + 1]) {
                    in[l]--;
                    m = 0;
                } else if (m && in[r] == out[r + 1]) {
                    in[r]--;
                    m = 0;
                } else break;
            }
            cnt_in = 0, cnt_out = 0;
            for (int i = 0; i < n; i++) {
                cnt_in += in[i];
                cnt_out += out[i];
            }
            if ((m == 0 && cnt_in == 0 && cnt_out == 1) || (m == 1 && cnt_in == cnt_out && cnt_in <= 1)) {
                cout << "TAK\n";
                continue;
            }

            cout << "NIE\n";
            continue;
        }

        if (start[0] == 0 || start[0] == n - 1) good = (n == 2);
        else if (start[0] != 0 && start[0] != n - 1) good = (n == 3);
        cout << (good ? "TAK\n" : "NIE\n");
    }
}