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

const int lim = 1'000'003, maint = 1'000'000'003;

int tab[lim];
int dp[lim];
bool dpb[lim];
int powr[lim];
bool powrb[lim];
int dp2[lim];
bool dp2b[lim];
int powr2[lim];
bool powr2b[lim];

int main(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for(int licz = 0; licz < t; licz++){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> tab[i];
        }
        bool czy_lew = 0, czy_cos = 0, coska = 0, ost = 0;
        dp[0] = -1;
        int l = -1, r = -1;
        for(int i = 1; i <= n; i++){
            if(l == -1 && tab[i] >= 1) l = i;
            if(tab[i] >= 1) r = i;
            if(tab[i] >= 1 && coska) ost = 1;
            if(l != -1 && tab[i] == 0) coska = 1; 
            if(tab[i] <= dp[i - 1]) dp[i] = -1;
            else dp[i] = tab[i] - 1 - dp[i - 1] - 1;
            
            powr[i] = tab[i] - 1 - min(dp[i - 1], tab[i] - 1);
        }
        dp2[n + 1] = -1;
        for(int i = n; i >= 1; i--){
            if(tab[i] <= dp2[i + 1]) dp2[i] = -1;
            else dp2[i] = tab[i] - 1 - dp2[i + 1] - 1;

            powr2[i] = tab[i] - 1 - min(dp2[i + 1], tab[i] - 1);
        }
        bool win = 0;
        dpb[l - 1] = 1;
        powrb[l - 1] = 1;
        for(int i = l; i <= r; i++){
            // cout << dp[i] << " " << dp2[i] << ' ' << powr[i] << ' ' << powr2[i] << "\n";
            dpb[i] = dpb[i - 1] & (dp[i] >= 0);
            powrb[i] = powrb[i - 1] & (powr[i] >= 0);
        }
        dp2b[r + 1] = 1;
        powr2b[r + 1] = 1;
        for(int i = r; i >= l; i--){
            dp2b[i] = dp2b[i + 1] & (dp2[i] >= 0);
            powr2b[i] = powr2b[i + 1] & (powr2[i] >= 0);
        }
        for(int i = l; i <= r; i++){
            // cout << dp[i] << " " << dp2[i] << ' ' << powr[i] << ' ' << powr2[i] << "\n";
        
            if(dpb[i] && dp2b[i]){
                // if(((- dp[i] - dp2[i] - 1) == -tab[i])) cout << i << "p1 \n";
                win |= ((-dp[i] - dp2[i] - 1) == -tab[i]);
            }
            if(dpb[i] && powr2b[i] && dp2b[i]){
                // if(((-dp[i] - powr2[i] - 1) == -tab[i])) cout << i << "p \n";
                win |= ((-dp[i] - powr2[i] - 1) == -tab[i]);
            }
            if(powrb[i] && dp2b[i] && dpb[i]){
                // if(((-dp2[i] - powr[i] - 1) == -tab[i])) cout << i << "p2 \n";
                win |= ((-dp2[i] - powr[i] - 1) == -tab[i]);
            }
            dp[i] = 0;
            dpb[i] = 0;
            dp2[i] = 0;
            dp2b[i] = 0;
            powr[i] = 0;
            powrb[i] = 0;
            powr2[i] = 0;
            powr2b[i] = 0;
        }

        if(win && !ost) cout << "TAK\n";
        else cout << "NIE\n";
    }
}