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

int main(){
    int n, k; cin >> n >> k;
    vector<int> a(n);

    int input;
    for(int i=0; i<n; i++){
        cin >> input;
        a[i] = input;
    }

    if (k > n){
        cout << "NIE\n";
    } else if(k == 2){
        vector<int> smallest_l(n);
        smallest_l[0] = a[0];
        for(int i=1; i<n; i++){
            smallest_l[i] = min(a[i], smallest_l[i-1]);
        }

        vector<int> biggest_r(n);
        biggest_r[n-1] = a[n-1];
        for(int i=n-2; i>=0; i--){
            biggest_r[i] = max(a[i], biggest_r[i+1]);
        }

        int result = 0;
        for(int i=1; i<n; i++){
            if(smallest_l[i-1] >= biggest_r[i]){
                result = i;
                break;
            }
        }

        if(result){
            cout << "TAK\n";
            cout << result << "\n";
        } else{
            cout << "NIE\n";
        }

    } else if(k == 3) {
        vector<int> smallest_l(n);
        smallest_l[0] = a[0];
        for(int i=1; i<n; i++){
            smallest_l[i] = min(a[i], smallest_l[i-1]);
        }

        vector<int> biggest_r(n);
        biggest_r[n-1] = a[n-1];
        for(int i=n-2; i>=0; i--){
            biggest_r[i] = max(a[i], biggest_r[i+1]);
        }

        int result1 = 0, result2 = 0;
        for(int i=1; i<n-1; i++){
            if((a[i] <= smallest_l[i-1]) || (a[i] >= biggest_r[i+1])){
                result1 = i;
                result2 = i+1;
                break;
            }
        }

        if(result1){
            cout << "TAK\n";
            cout << result1 << " " << result2 << "\n";
        } else{
            cout << "NIE\n";
        }
    } else {
        vector<int> result(k-1);
        for(int i=0; i<k-1; i++) result[i] = -1;
        int lIndex = -1;
        for(int i=1; i<n; i++){
            if(a[i] <= a[i-1]){
                if(i == 1){
                    result[0] = i;
                    result[1] = i+1;
                    lIndex = 1;
                } else if(i == n-1){
                    result[k-2] = i;
                    result[k-3] = i-1;
                    lIndex = k-3;
                } else{
                    int fIndex = 0;
                    if(i+k-3 >= n){
                        fIndex = i+k-n-2;
                    }
                    result[fIndex] = i-1;
                    result[fIndex+1] = i;
                    result[fIndex+2] = i+1;
                    lIndex = fIndex+2;
                }
                break;
            } 
        }
        if(lIndex == -1){
            cout << "NIE\n";
        } else {
            while(lIndex < k-2){
                result[lIndex+1] = result[lIndex]+1; 
                lIndex++;
            }
            lIndex = 0;
            while(lIndex < k-1 && result[lIndex] == -1){
                result[lIndex] = lIndex+1;
                lIndex++;
            }

            cout << "TAK\n";
            for(int x: result){
                cout << x << " ";
            }
            cout <<"\n";
        }
    }
}