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

using namespace std;

#define ll long long

const ll MAXN = 1e6 + 7;
ll tab[MAXN];

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll T;
	cin >> T;
	while(T--){
		ll n;
		cin >> n;
		ll ost = 0;
		ll p = 0;
		tab[0] = 0;
		for(ll i = 1; i <= n ; i++){
            tab[i] = 0;
			cin >> tab[i];
			if(tab[i] != 0){
				ost = i;
			}
			if(ost == 0 && tab[i] == 0){
				p = i;
			}
		}
        tab[n+1] = 0;
        //cerr << p << " " << ost << "\n";
		bool czy = true;
        ll sum = 0;
		ll diff = 0;
        for(ll i = 1 ; i <= n; i++){
            if(tab[i-1] == 0 && tab[i] != 0){
				diff++;
			}
        }
		if(diff > 1){
			cout << "NIE\n";
			continue;
		}
		//cerr << ost << "\n";
		for(ll i = 1; i <= n ; i++){
			// for(ll i = 1; i <= n ; i++){
			// 	cerr << tab[i] << " ";
			// }cerr << "\n";
			if((tab[i] > 0 && tab[i+1] > 0) && (tab[i] > 1 || tab[i+1] > 1)){
                ll k = min(tab[i]-1, tab[i+1]-1);
				
				if(tab[i] != tab[i+1]){
					if(tab[i] > tab[i+1]){
						k = min(tab[i], tab[i+1]);
					}
					else{
						if(sum == 0){
							k = min(tab[i], tab[i+1]);
						}
					}
				}

                tab[i] -= k;
                tab[i+1] -= k;
            }
            sum += tab[i];
		}
		diff = 0;
        ll maks = 0;
        for(ll i = 1; i <= n+1 ; i++){
            if(tab[i] != tab[i-1]){
                diff++;
            }
            maks = max(maks, tab[i]);
        }

		if(diff <= 2 && maks <= 1){
			cout << "TAK\n";
		}
		else{
			cout << "NIE\n";
		}
	}

	return 0;
}