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

using namespace std;
#define nd second
#define st first
#define pb push_back
typedef long long ll;
typedef long double ld;
const int N = 5 * 100 * 1000 + 7;
int tab[N], mi[N], ma[N];
bool cz[N];

void AnsK3(int n)
{
    mi[1] = tab[1]; ma[n] = tab[n];
    for(int i = 2; i <= n; ++i)
        mi[i] = min(mi[i - 1], tab[i]);
    for(int i = n - 1; i >= 1; --i)
        ma[i] = max(ma[i + 1], tab[i]);
    for(int i = 2; i < n; ++i)
    {
        if(mi[i - 1] >= tab[i] || ma[i + 1] <= tab[i])
        {
            cout << "TAK\n";
            cout << i - 1 << " " << i << "\n";
            return;
        }
    }
    cout << "NIE\n";
}

void AnsK2(int n)
{
    mi[1] = tab[1]; ma[n] = tab[n];
    for(int i = 2; i <= n; ++i)
        mi[i] = min(mi[i - 1], tab[i]);
    for(int i = n - 1; i >= 1; --i)
        ma[i] = max(ma[i + 1], tab[i]);
    for(int i = 1; i < n; ++i)
    {
        if(mi[i] >= ma[i + 1])
        {
            cout << "TAK\n";
            cout << i << "\n";
            return;
        }
    }
    cout << "NIE\n";
}

void Solve()
{
    int n, k, si = 0; bool xd = false;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tab[i];
        if(i > 1 && tab[i] <= tab[i - 1] && !xd)
        {
            si = i;
            xd = true;
        }
    }
    if(!xd)
    {cout << "NIE\n"; return;}
    if(k == 2)
    {AnsK2(n); return;}
    if(k == 3)
    {AnsK3(n); return;}
    cz[si] = true; cz[si - 2] = 1; cz[si - 1] = true; cz[n] = true;
    k -= 4;
    if(si == n) ++k;
    if(si == 2) ++k;
    cout << "TAK\n";
    for(int i = 1; i < n; ++i)
    {
        if(k > 1 && !cz[i])
        {--k; cz[i] = true;}
        if(cz[i])
            cout << i << " ";
    }
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}