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
#include <bits/stdc++.h>
using namespace std;
int n, m, k, t[500005], t2[500005];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &t[i]);
    }
    if (m == 2)
    {
        t2[0] = t[0];
        for (int i = 1; i < n; ++i)
        {
            t2[i] = min(t2[i - 1], t[i]);
        }
        int mx = t[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            if (mx <= t2[i])
            {
                printf("TAK\n%d", i + 1);
                return 0;
            }
        }
        printf("NIE");
        return 0;
    }
    if (m == 3)
    {
        int mn = INT_MAX, mx = 0, in = 0, ix = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mx == t[i])
                ++ix;
            if (mx < t[i])
            {
                mx = t[i];
                ix = 1;
            }
            if (mn == t[i])
                ++in;
            if (mn > t[i])
            {
                mn = t[i];
                in = 1;
            }
        }
        if (mn == t[0] && mx == t[n - 1] && in == 0 && ix == 0)
        {
            printf("NIE");
            return 0;
        }
        int a;
        if (mn != t[0] || in > 1)
            a = mn;
        if (mx != t[n - 1] || ix > 1)
            a = mx;
        for (int i = 1; i < n; ++i)
        {
            if (t[i] == a)
            {
                printf("TAK\n%d %d", i, i + 1);
                return 0;
            }
        }
    }
    int a = -1, b = -1;
    for (int i = 1; i < n; ++i)
    {
        if (t[i - 1] >= t[i])
        {
            a = t[i - 1];
            b = t[i];
            break;
        }
    }
    if (a == -1)
    {
        printf("NIE");
        return 0;
    }
    m -= 4;
    printf("TAK\n");
    for (int i = 0; i < a && m > 0; ++i)
    {
        printf("%d ", i + 1);
        --m;
    }
    printf("%d %d ", a + 1, b + 1);
    for (int i = b + 1; i < n && m > 0; ++i)
    {
        printf("%d ", i + 1);
        --m;
    }
    return 0;
}