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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// O(n log n) solution
// case 1: k = 2 -> max on the last edge -> NIE, else -> TAK CHECKME:
// case 2: k > 2 minimum or/and maximum not on edges CHECKME: print
// case 3: k = 3, minimum and maximum on edges, not entirely sorted -> NIE CHECKME: print
// case 4: k >= 4, minmum and maximum on edges, not entirely sorted take any inversion and put it in 2 one-element segments CHECKME: print
#include <bits/stdc++.h>
using namespace std;

// Errichto's sparse table
const int MAX_N = 5e5 + 5;
const int LOG = 19;
int m[MAX_N][LOG]; // m[i][j] is maximum among a[i..i+2^j-1]
int bin_log[MAX_N];

int query(int L, int R)
{
    int length = R - L + 1;
    int k = bin_log[length];
    return max(m[L][k], m[R - (1 << k) + 1][k]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, myn = 0, maks = 0;
    cin >> n >> k;
    vector<int> A(n);
    for (auto &x : A)
        cin >> x;
    for (int i = 1; i < n; ++i)
    {
        if (A[i] > A[maks]) // first maximum
            maks = i;
        if (A[i] <= A[myn]) // last minimum
            myn = i;
    }
    if (k == 2)
    {
        // case 1
        bin_log[1] = 0;
        for (int i = 2; i <= n; i++)
            bin_log[i] = bin_log[i / 2] + 1;
        for (int i = 0; i < n; i++)
            m[i][0] = A[i];
        for (int k = 1; k < LOG; k++)
        {
            for (int i = 0; i + (1 << k) - 1 < n; i++)
                m[i][k] = max(m[i][k - 1], m[i + (1 << (k - 1))][k - 1]);
        }
        int curmin = INT_MAX;
        for (int i = 0; i < n - 1; ++i) // segment can have up to n-1 elements
        {
            curmin = min(curmin, A[i]);
            if (curmin >= query(i + 1, n - 1))
            {
                cout << "TAK" << endl;
                cout << i + 1 << endl;
                return 0;
            }
        }
        cout << "NIE" << endl;
        return 0;
    }
    else
    {
        // case 3 and 4
        if (myn == 0 && maks == n - 1)
        {
            // case 3
            if (k == 3)
            {
                cout << "NIE" << endl;
                return 0;
            }
            // case 4
            int pos = -1;
            for (int i = 1; i < n; ++i)
            {
                if (A[i] <= A[i - 1])
                {
                    pos = i;
                    break;
                }
            }
            if(pos == -1)
            {
                cout << "NIE\n";
                return 0;
            }
            cout << "TAK" << endl;
            for (int i = 1; i <= n; ++i)
            {
                if (k > 4 || (i == pos || i == pos + 1 || i == pos - 1)) // TODO: overflow
                {
                    cout << i << " ";
                    --k;
                }
                if (i > pos + 1 && k > 1)
                {
                    cout << i << " ";
                    --k;
                }
            }
            return 0;
        }
        // case 2 -> k > 2 minimum or/and maximum not on edges
        if (myn != 0 || maks != n - 1)
        {
            cout << "TAK" << endl;
            // cout << "XD" << endl;
            // cout << myn << " " << maks << endl;
            int pos = 0;
            if (maks != n - 1)
                pos = maks;
            else
                pos = myn;
            // cout << pos << endl;
            ++pos;
            for (int i = 1; i <= n; ++i)
            {
                if (k > 4 || ((i == pos + 1 || i == pos || i == pos - 1) && k > 1)) // TODO: overflow
                {
                    cout << i << " ";
                    --k;
                }
                else if (i > pos && k > 1)
                {
                    cout << i << " ";
                    --k;
                }
            }
            return 0;
        }
    }
}