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

using namespace std;

const int N = 5e5+1;

int a[N], mn[N], mx[N], n, k;
bool us[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for (int i=1; i<=n; ++i) cin>>a[i];

    bool inc=true;
    for (int i=1; i<n; ++i) {
        if (a[i] >= a[i+1]) inc=false;
    }

    if (inc) {
        cout<<"NIE\n";
        return 0;
    }

    mn[1]=a[1], mx[n]=a[n];
    for (int i=2; i<=n; ++i) mn[i]=min(mn[i-1], a[i]);
    for (int i=n-1; i>=1; --i) mx[i]=max(mx[i+1], a[i]);

    vector<int> v;
    if (k >= 4) {
        int i=1;
        for (i=1; i<n; ++i) {
            if (a[i] >= a[i+1]) break;
        } assert(a[i] >= a[i+1]);

        v.push_back(i); us[i]=true;
        if (i+1 < n) v.push_back(i+1), us[i+1]=true;
        if (i-1 >= 1) v.push_back(i-1), us[i-1]=true;

        for (int i=1; i<=n && (int)v.size() < k-1; ++i) {
            if (us[i]) continue;
            v.push_back(i), us[i]=true;
        }

        if (v.empty()) {
            cout<<"NIE\n";
            return 0;
        }

    } else if (k == 3) {
        for (int i=1; i<n; ++i) {
            if (mn[i] >= a[i+1]) {
                v.push_back(i);

                if (i+1 < n) v.push_back(i+1);
                else v.push_back(1);
                break;
            }
        }

        for (int i=n; i>1 && v.empty(); --i) {
            if (a[i-1] >= mx[i]) {
                v.push_back(i-1);
                if (i+1 < n) v.push_back(i+1);
                else v.push_back(1);
            }
        }

        if (v.empty()) {
            cout<<"NIE\n";
            return 0;
        }
    } else {
        assert(k == 2);
        for (int i=1; i<n; ++i) {
            if (mn[i] >= mx[i+1]) {
                v.push_back(i);
                break;
            }
        }

        if (v.empty()) {
            cout<<"NIE\n";
            return 0;
        }
    }

    cout<<"TAK\n";
    sort(v.begin(), v.end());
    for (auto u : v) cout<<u<<" ";
    cout<<"\n";
}