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

#define cerr if (0) cout

int check_2(const vector<int>& tab, int l, int r) {
    int minal = tab[l];
    multiset<int> rset;
    for (int i = l + 1; i < r; ++i) {
        rset.insert(tab[i]);
    }

    if (minal >= *--rset.end()) {
        return l;
    } else {
        for (int i = l + 1; i < r - 1; ++i) {
            minal = min(minal, tab[i]);
            rset.erase(rset.find(tab[i]));

            cerr << "RSET3: "; for (auto p : rset) cerr  << p << " "; cerr << endl;

            if (minal >= *--rset.end()) {
                return i;
            } 
        }

    }
    return -1;
}

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

    int N, K; cin >> N >> K;

    vector<int> tab(N);
    vector<int> result;
    result.reserve(K);

    for (int i = 0; i < N; ++i) {
        cin >> tab[i];
    }

    int glob_min_pos = min_element(tab.begin(), tab.end()) - tab.begin();
    int glob_max_pos = max_element(tab.begin(), tab.end()) - tab.begin();

    auto divs = K - 1;
    int l = 0, r = N;

    if (divs == 1)
    {
        int res = check_2(tab, l, r);
        if (res != -1) {
            divs -= 1;
            result.push_back(res);
        }
    }
    else if (divs == 2)
    {
        if (glob_max_pos != r - 1 || glob_min_pos != l) {
            // cerr << "e2" << endl;
            if (glob_max_pos != r - 1) {
                // clog << "Xd\t"<< glob_max_pos << endl;
                divs -= 2;

                if (glob_max_pos != 0) {
                    // clog << "Xde\n";
                    result.push_back(glob_max_pos - 1);
                    result.push_back(glob_max_pos);
                }
                else {
                    // clog << "Xdf\n";
                    result.push_back(glob_max_pos);
                    result.push_back(glob_max_pos + 1);
                }
            } else {
                // clog << "Xd2\n";
                divs -= 2;

                result.push_back(glob_min_pos - 1);
                result.push_back(glob_min_pos);
            }
        }
        else 
        {
            // clog << "Xd3\n";
            int lres = check_2(tab, l + 1, r);
            if (lres != -1) {
                result.push_back(l);
                result.push_back(lres);
                divs -= 2;
            }
            else {
                int rres = check_2(tab, l, r - 1);
                if (rres != -1) {
                    result.push_back(rres);
                    result.push_back(r - 1);
                    divs -= 2;
                } 
            }
        }
    }
    else if (divs >= 3) 
    {
        int inv_index = -1;
        for (int i = 1; i < r; ++i) {
            if (tab[i - 1] >= tab[i]) {
                inv_index = i;
                break;
            }
        }

        // cerr << "INV\t" << inv_index << "\t" << tab[inv_index] << "\t" << tab[inv_index - 1] << "\n";

        if (inv_index > 0 ) 
        {
            divs -= 2;

            if (inv_index != 1) divs -= 1;

            for (int i = l; i < inv_index - 1 && divs; ++i) {
                result.push_back(i);
                divs -= 1;
            }

            if (inv_index != 1)result.push_back(inv_index - 2);
            result.push_back(inv_index - 1);
            result.push_back(inv_index);

            for (int i = inv_index + 1; i < r && divs; ++i) {
                result.push_back(i);
                divs -= 1;
            }
        }
    }

    // cerr << "divs: " << divs << endl;

    if (divs == 0) {
        cout << "TAK\n";
        sort(begin(result), end(result));
        for(auto p : result) cout << p + 1 << " ";
    } else {
        cout << "NIE\n";
    }

    return 0;
}