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

// make the code less c++-readable:
template<class T> using v = vector<T>; 
template<class T> using vv = v<v<T>>; 
using vi = v<int>; using vll = v<ll>; using vvi = vv<int>; using vvll = vv<ll>;

// hai loading utilities
#define $T template<class T>
#define $Ts template<class... T>
$T T Load() { T v; cin >> v; return v; }
$T auto Loads(int n) { v<T> v; v.reserve(n); while(n--) v.emplace_back(Load<T>()); return v; }
$T auto Loads() { return Loads<T>(Load<int>()); }
template<class T, int N> auto Loada() { array<T, N> a; for (T& v: a) v = Load<T>(); return a; }
$Ts auto Cols(int rows) { tuple<v<T>...> t; while(rows--) [&]<sz... I>(index_sequence<I...>){(std::get<I>(t).push_back(Load<T>()), ...);}(index_sequence_for<T...>{}); return t; }
//$Ts auto Rows(int rows) { v<tuple<T...>> v; while(rows--) { v.emplace_back(Load<T>()...); } return v; } bugged :(
struct _aIV { $T operator vector<T>() { return Loads<T>(n); } sz n; };
struct _aI { $T operator T() { return Load<T>(); } _aIV operator()(sz n) { return {n}; } }; static inline _aI $;  /* int N = $;  vi Y = $(N); */
#define MAKE_LOADER(T, alias) \
  T alias() { return Load<T>(); }   /* int x = Int(); */\
  auto alias##s() { return Loads<T>(); }   /* vector<> xs = Ints(); */\
  auto alias##s(int n) { return Loads<T>(n); }   /* vector<> xs = Ints(7); */\
  template<int N> auto alias##a() { return Loada<T, N>(); }   /* array<> xs = Inta<7>();  */\
// line intentionally left blank
MAKE_LOADER(int, Int)
MAKE_LOADER(long long, LL)
MAKE_LOADER(char, Char)
MAKE_LOADER(string, String)
// kthxbye


enum JakTam { Świetnie, Średnio, Źle };

void test() {    
    vector<int> wskazania = Ints();
    
    int p1 = 0;
    int p2 = wskazania.size() - 1;
    
    auto Zrób = [&](int ten, int następny, bool zeruj = false) {      
        JakTam jest;
        if (wskazania[następny] > wskazania[ten] || wskazania[ten] == 0) jest = Świetnie;
        else if (zeruj && wskazania[następny] >= wskazania[ten]) jest = Świetnie;
        else if (wskazania[następny] == wskazania[ten]) jest = Średnio;
        else return Źle;
                
        const int obniżka = zeruj ?
            min(wskazania[ten], wskazania[następny]) :
            max(0, min(wskazania[ten], wskazania[następny]-1));
        wskazania[ten] -= obniżka;
        wskazania[następny] -= obniżka;
        return jest;
    };
    
    auto KajPoczątek = [&](int& p, int& innyp, int kierun) {        
        while ((p + kierun)*kierun <= innyp*kierun) {
            const JakTam jest = Zrób(p, p+kierun);
            if (jest != Świetnie) break;            
            p += kierun;
        }
    };
    
    KajPoczątek(p1, p2, +1);
    KajPoczątek(p2, p1, -1);
    
    if (p1 == p2) {
        if (wskazania[p1] <= 1)
            cout << "TAK" << endl;
        else
            cout << "NIE" << endl;
        return;
    }
    
    
    // Dekreskacja
    for (int i = p1; i <= p2; ++i) {
        if (wskazania[i] < 1) {
            cout << "NIE" << endl; return;
        }
        wskazania[i]-=1;
    }
        
    for (int i = 0; i < wskazania.size()-1; ++i) {
        if (Zrób(i, i+1, true) != Świetnie) {
            cout << "NIE" << endl; return;
        }
    }
    if (wskazania.back() != 0) {
        cout << "NIE" << endl; return;
    }
    
    cout << "TAK" << endl;
}

[[maybe_unused]] void jeden_test() { test(); }
[[maybe_unused]] void wiele_test() { int T = $; while (T--) test(); }

int main() {
    wiele_test();
    return 0;
}