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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <bits/stdc++.h>
using namespace std;

/*
  Funkcja sprawdza, czy ciąg a[1..n] może pochodzić z opisanej wyliczanki.
  Zwraca true, jeśli tak, albo false w przeciwnym razie.
*/
bool canBeGenerated(const vector<long long> &a) {
    int n = (int)a.size();

    // 1. Znajdujemy L i R - pierwszy i ostatni indeks z a_i > 0
    int L = 0;
    while (L < n && a[L] == 0) L++;
    if (L == n) {
        // Wszystko 0? A zadanie mówi, że co najmniej jedna liczba jest niezerowa,
        // więc teoretycznie nie powinno się zdarzyć. Ale zabezpieczmy się.
        return false;
    }
    int R = n-1;
    while (R >= 0 && a[R] == 0) R--;
    
    // 2. Zliczamy sumę wizyt (sumAll) oraz sumę na indeksach parzystych i nieparzystych
    // Uwaga: w C++ indeksy są 0-based, a w treści zadania 1-based.
    // Parzystość "zadaniowa" dla i = 1-based to (i % 2).
    // Zatem "zadaniowy" indeks i = real_index+1.
    // => parzysty zadaniowo, gdy (real_index+1) % 2 == 0 => real_index % 2 == 1.
    long long sumAll = 0, sumOdd = 0, sumEven = 0;
    for (int i = L; i <= R; i++) {
        sumAll += a[i];
        if (((long long)i + 1) % 2 == 1) {
            // i+1 nieparzyste -> to "odd" w zadaniu
            sumOdd += a[i];
        } else {
            sumEven += a[i];
        }
    }
    // 3. Sprawdzamy warunek parzystości
    if (sumAll % 2 == 0) {
        // sumAll parzyste => sumOdd == sumEven
        if (sumOdd != sumEven) return false;
    } else {
        // sumAll nieparzyste => |sumOdd - sumEven| == 1
        long long diff = sumOdd - sumEven;
        if (std::llabs(diff) != 1) return false;
    }

    // Przypadki proste
    // - jeśli w podprzedziale [L,R] mamy tylko jedną zabawkę (L==R)
    //   to da się ją wskazać tyle razy, ile a[L], TYLKO gdy a[L] == 1;
    //   inaczej brak możliwości ruchu
    if (L == R) {
        // Mamy tylko jedną zabawkę w użyciu:
        if (a[L] == 1) return true;
        else return false;
    }

    // Jeśli sumAll == 1, to musi być dokładnie jedna zabawka=1, reszta=0 (już wiemy [L,R] ma długość > 1 => sprzeczność)
    if (sumAll == 1) {
        // Wprawdzie tu R>L, więc w sumie mogłyby być dwie zabawki, z czego jedna=1, druga=0.
        // Ale to by oznaczało, że L i R to ta sama zabawka, co sprzecza się z (R>L).
        return false;
    }

    // 4. Zgodnie z omówieniem - próbujemy wybrać punkt startu i końca,
    //    pamiętając, że jeśli sumAll parzyste, to start i koniec mają różną parzystość (w sensie i+1).
    //    Jeśli nieparzyste, to mają tę samą parzystość. Dodatkowo a[start], a[end] > 0.
    //    W praktyce dla sumAll nieparzystego wiadomo, która parzystość "ma przewagę" (sumOdd > sumEven czy odwrotnie).

    // Pomocnicza lambda zwracająca "parzystość zadaniową" (1-based) danego indeksu:
    auto parity1based = [&](int idx) {
        // idx: 0-based
        // idx+1: 1-based
        return ( (idx+1) % 2 ); 
    };

    // Zbierzmy kandydatów na start (parStart) i koniec (parEnd).
    // Będziemy próbować maksymalnie 2 warianty (gdy sumAll parzyste).
    vector<pair<int,int>> candidates;

    if (sumAll % 2 == 0) {
        // Muszą być różne parzystości: (start_par, end_par) = (0,1) lub (1,0)
        // w sensie "zadaniowym" 0/1. Szukamy w całym [L,R], byle a[i]>0.
        // parStart=0 => to znaczy (i+1)%2=0 => i %2=1 w 0-based
        // parEnd=1   => to znaczy (j+1)%2=1 => j %2=0 w 0-based
        // i odwrotnie.
        candidates.push_back({0,1});
        candidates.push_back({1,0});
    } else {
        // |sumOdd - sumEven|=1 => start i koniec mają tę samą parzystość, którą jest "większa".
        long long diff = sumOdd - sumEven; // może być +1 albo -1
        // jeśli diff=+1 => sumOdd>sumEven => start+end = nieparzyste (1 w 1-based),
        // czyli i %2=0 w 0-based
        // jeśli diff=-1 => start+end = parzyste (0 w 1-based),
        // czyli i %2=1 w 0-based
        if (diff == 1) {
            // start/end w 1-based=nieparzyste => 0-based %2=0
            candidates.push_back({1,1}); // w sensie "zadaniowej" parzystości =1 (nieparzysty indeks)
        } else {
            // diff==-1
            candidates.push_back({0,0}); // w sensie "zadaniowej" parzystości =0 (parzysty indeks)
        }
    }

    // Funkcja pomocnicza: sprawdza, czy w [L,R] można ustawić start i koniec
    // o zadanych parzystościach "zadaniowych" (parS, parE) tak, by a[i]>0 i a[j]>0.
    // Jeśli tak, to weryfikuje warunek "parzystości odwiedzin" w środku:
    auto checkCandidate = [&](int parS, int parE) -> bool {
        // Szukamy jakiegokolwiek i w [L..R], że parity1based(i) == parS i a[i]>0
        // oraz jakiegokolwiek j w [L..R], że parity1based(j) == parE i a[j]>0.
        // Jeśli parS==parE, dopuszczalne jest i=j, jeśli a[i]>=2.
        vector<int> starts, ends;
        for (int x = L; x <= R; x++) {
            if (a[x] > 0 && parity1based(x) == parS) {
                starts.push_back(x);
            }
        }
        for (int x = L; x <= R; x++) {
            if (a[x] > 0 && parity1based(x) == parE) {
                ends.push_back(x);
            }
        }
        if (starts.empty() || ends.empty()) return false;

        // Spróbujemy każdą parę (start, end). W praktyce nie jest ich dużo,
        // bo wystarczy wziąć np. pierwszą i ostatnią pozycję z listy starts/ends.
        // Ale dla bezpieczeństwa w tym przykładzie sprawdzamy wszystkie.
        // W realnym kodzie można by się ograniczyć do 2-3 prób (np. skrajnych indeksów),
        // bazując na obserwacjach, że i tak jeśli gdzieś jest możliwa ścieżka, to
        // da się ją "przesunąć" do odpowiednich brzegów. Ale tu pokażemy pełne sprawdzenie.

        for (int s : starts) {
            for (int e : ends) {
                // Jeśli s==e, trzeba mieć a[s]>=2, by "zdjąć" 2 wizyty na start=end.
                if (s == e && a[s] < 2) continue;

                // Tymczasowo modyfikujemy tablicę (kopia) i sprawdzamy parzystości w środku:
                // - odejmujemy 1 z a[s], 1 z a[e], albo 2 jeśli to ta sama zabawka
                bool ok = true;
                // kopiuj do tymczasowego wektora
                static thread_local vector<long long> tmp; 
                tmp = a;

                if (s == e) {
                    tmp[s] -= 2;
                    if (tmp[s] < 0) ok = false;
                } else {
                    tmp[s] -= 1;
                    tmp[e] -= 1;
                    if (tmp[s] < 0 || tmp[e] < 0) ok = false;
                }
                if (!ok) continue;

                // Teraz sprawdzamy dla każdej zabawki wewnątrz [L,R]:
                // - jeśli nie jest (start ani end), to liczba wizyt powinna być parzysta,
                //   a przy brzegach (L,R) dodatkowo, jeśli nie s/e, to też parzysta.
                // Ogólnie: jeśli zabawka i ∉ {s,e}, to tmp[i] powinno być parzyste.
                for (int i = L; i <= R && ok; i++) {
                    if (i == s || i == e) continue; // już zmniejszyliśmy tu liczbę odwiedzin
                    if (tmp[i] % 2 != 0) {
                        ok = false;
                    }
                }
                if (ok) {
                    return true; // udało się
                }
            }
        }
        return false;
    };

    // Sprawdzamy wszystkie warianty start-koniec z listy candidates
    for (auto &c : candidates) {
        int parS = c.first, parE = c.second;
        if (checkCandidate(parS, parE)) {
            return true;
        }
    }

    // Jeśli żaden wariant nie przeszedł – odpowiadamy NIE
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; 
    cin >> t;
    while (t--) {
        int n; 
        cin >> n;
        vector<long long> a(n);
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        if(canBeGenerated(a)){
            cout << "TAK\n";
        } else {
            cout << "NIE\n";
        }
    }
    return 0;
}