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

using namespace std;

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

    int n, k; cin >> n >> k;
    vector<int> v(n);
    for (auto& e : v)
        cin >> e;

    if (k >= 4)
    {
        bool strictly_increasing = true;
        int idx = 0;
        for (; idx < (int)v.size()-1; idx++)
            if (v[idx] >= v[idx+1])
            {
                strictly_increasing = false;
                break;
            }

        if (strictly_increasing)
            cout << "NIE\n";
        else
        {
            cout << "TAK\n";
            if (idx < k-2)
            {
                for (int i = 0; i < k-1; i++)
                    cout << i+1 << " ";
                cout << "\n";
            }
            else if (idx > (int)v.size()-k)
            {
                for (int i = v.size()-k; i < (int)v.size()-1; i++)
                    cout << i+1 << " ";
                cout << "\n";
            }
            else
            {
                int front = (k-1-3)/2;
                int back = k-1-3 - front;

                for (int i = 0; i < front; i++)
                    cout << i+1 << " ";

                cout << idx << " " << idx + 1 << " " << idx +2 << " ";

                for (int i = v.size()-1-back; i < (int)v.size()-1; i++)
                      cout << i+1 << " ";
                cout << "\n";
            }
        }
    }
    else if (k == 3)
    {
        vector<int> prefix_min(v.size());
        prefix_min[0] = v[0];
        for (int i = 1; i < (int)v.size(); i++)
            prefix_min[i] = min(prefix_min[i-1], v[i]);

        vector<int> sufix_max(v.size());
        sufix_max[v.size()-1] = v[v.size()-1];
        for (int i = (int)v.size()-1; i-- > 0; )
            sufix_max[i] = max(sufix_max[i+1], v[i]);

        int idx = -1;
        for (int i = 1; i < (int)v.size()-1; i++)
            if (prefix_min[i-1] >= v[i] || v[i] >= sufix_max[i+1])
            {
                idx = i;
                break;
            }

        if (idx == -1)
            cout << "NIE\n";
        else
            cout << "TAK\n" << idx << " " << idx+1 << "\n";
    }
    else if (k == 2)
    {
        vector<int> prefix_min(v.size());
        prefix_min[0] = v[0];
        for (int i = 1; i < (int)v.size(); i++)
            prefix_min[i] = min(prefix_min[i-1], v[i]);

        vector<int> sufix_max(v.size());
        sufix_max[v.size()-1] = v[v.size()-1];
        for (int i = (int)v.size()-1; i-- > 0; )
            sufix_max[i] = max(sufix_max[i+1], v[i]);

        int idx = -1;
        for (int i = 0; i < (int)v.size()-1; i++)
            if (prefix_min[i] >= sufix_max[i+1])
            {
                idx = i;
                break;
            }

        if (idx == -1)
            cout << "NIE\n";
        else
            cout << "TAK\n" << idx+1 << "\n";
    }
}