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
#include <bits/stdc++.h>
using namespace std;
const int m = 1 << 16;
int tab[500008], drzewo[(m+1)*2]; bool indeks[500008], w = true;
vector <int> przedzialy;

void Punkt(int w, int val) {
    w += m-1;
    while(w) {
        drzewo[w] += val;
        w /= 2;
    }
}

int mx_przedzial(int w, int p, int k, int x, int y) {
    if(x > k || y < p) return 0;
    else if(x >= p && y <= k) return drzewo[w];
    else return max(mx_przedzial(2*w, p, k, x, (x+y)/2), mx_przedzial(2*w+1, p, k, (x+y)/2 + 1, y));
}

int mn_przedzial(int w, int p, int k, int x, int y) {
    if(x > k || y < p) return 0;
    else if(x >= p && y <= k) return drzewo[w];
    else {
        int w1 = mn_przedzial(w*2, p, k, x, (x+y)/2);
        int w2 = mn_przedzial(w*2 + 1, p, k, (x+y)/2 + 1, y);
        if(w1 != 0 && w2 != 0) return min(w1, w2);
        else if(w1 == 0 && w2 != 0) return w2;
        else return w1;
    }
}

int main() {
    int n, k; cin >> n >> k;
    int mn = 1000000008, mx = 0, indeksmn = 0, indeksmx = n;
    for (int i = 1; i <= n; i++) {
        cin >> tab[i];
        Punkt(i, tab[i]);
        if(tab[i] <= mn) {
            mn = tab[i];
            indeksmn = i;
        }
        if(tab[i] >= mx) {
            mx = tab[i];
            indeksmx = i;
        }
    }
    int akt_k = k-1;
    if(k == 2) {
        w = false;
        for (int i = 1; i <= n; i++) {
            if(mx_przedzial(1, i+1, n, 1, m) <= mn_przedzial(1, 1, i, 1, m)) {
                przedzialy.push_back(i);
                break;
            }
        }
    }
    else {
        if(indeksmn != 1) {
            if(indeksmn == n) {
                akt_k--;
                przedzialy.push_back(indeksmn);
                indeks[indeksmn] = true;
            }
            else {
                akt_k -= 2;
                przedzialy.push_back(indeksmn);
                przedzialy.push_back(indeksmn-1);
                indeks[indeksmn] = true;
                indeks[indeksmn-1] = true;
            }
        }
        else if(indeksmx != n) {
            if(indeksmx == 1) {
                akt_k--;
                przedzialy.push_back(indeksmx);
                indeks[indeksmx] = true;
            }
            else {
                akt_k -= 2;
                przedzialy.push_back(indeksmx);
                przedzialy.push_back(indeksmx-1);
                indeks[indeksmx] = true;
                indeks[indeksmx-1] = true;
            }
        }
        else {
            w = false;
        }
        if(akt_k%2 == 1 && w == true) {
            if(!indeks[n]) {
                indeks[n] = true;
                akt_k--;
            }
            else if(!indeks[1]) {
                indeks[1] = true;
                akt_k--;
            }
            else w = false;
        }
        for (int i = 2; i < n; i++) {
            if(!akt_k || w == false) break;
            if(!indeks[i]) {
                przedzialy.push_back(i);
                przedzialy.push_back(i-1);
                akt_k--;
            }
        }
    }
    if(w == false) cout << "NIE\n";
    else {
        cout << "TAK\n"; 
        sort(przedzialy.begin(), przedzialy.end());
        for (int i = 0; i < przedzialy.size(); i++) cout << przedzialy[i] << " ";
    }
}