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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int resultFromSolve(vector<int>& nums) {
    int n = nums.size();
    vector<int> leftMins(n), rightMaxs(n);
    leftMins[0] = nums[0], rightMaxs[n - 1] = nums[n - 1];
    for(int i = 1; i < n; ++i) {
        leftMins[i] = min(leftMins[i - 1], nums[i]);
    }
    for(int i = n - 2; i >= 0; --i) {
        rightMaxs[i] = max(rightMaxs[i + 1], nums[i]);
    }
    for(int i = 0; i < n - 1; ++i) {
        if(leftMins[i] >= rightMaxs[i + 1]) {
            return i + 1;
        }
    }
    return -1;
}

void solve2(vector<int>& nums) {
    int res = resultFromSolve(nums);
    if(res == -1) {
        cout << "NIE\n";
    } else {
        cout << "TAK\n";
        cout << res << "\n";
    }
}

void solve3(vector<int>& nums) {
    int n = nums.size();
    int maxValue = 0, maxPosition = n;
    for(int i = n - 1; i >= 0; --i) {
        if(nums[i] >= maxValue) {
            maxValue = nums[i];
            maxPosition = i;
        }
    }
    if(maxPosition == n - 1) {
        nums.pop_back();
        int point = resultFromSolve(nums);
        if(point == -1) {
            cout << "NIE\n";
        } else {
            cout << "TAK\n";
            cout << point << " " << n - 1 << "\n";
        }
    } else {
        cout << "TAK\n";
        cout << maxPosition << " " << maxPosition + 1 << "\n";
    }
}

void solvek(const vector<int>& nums, int k) {
    int n = nums.size();
    int breakPosition = -1;
    for(int i = 1; i < n; ++i) {
        if(nums[i] <= nums[i - 1]) {
            breakPosition = i;
            break;
        }
    }
    if(breakPosition == -1) {
        cout << "NIE\n";
    } else {
        int left = k - 2;
        cout << "TAK\n";
        vector<int> result;
        result.push_back(breakPosition);
        result.push_back(breakPosition + 1);
        if(result[1] != n) {
            --left;
            result.push_back(n);
        }
        int position = breakPosition - 1;
        while(position >= 1 && left > 0) {
            result.push_back(position);
            --position;
            --left;
        }
        position = breakPosition + 2;
        while(position < n && left > 0) {
            result.push_back(position);
            ++position;
            --left;
        }
        sort(result.begin(), result.end());
        for(int i = 0; i < result.size() - 1; ++i) {
            cout << result[i] << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    if(k == 2) {
        solve2(nums);
    } else if(k == 3) {
        solve3(nums);
    }
    else {
        solvek(nums, k);
    }
}