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

int main() {

    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for(int i=0; i<n; ++i) std::cin>>a[i];

    std::vector<int> min(n);
    std::vector<int> max(n);

    min[0] = a[0];
    for(int i=1; i<n; ++i) min[i] = std::min(min[i-1], a[i]);
    max[n-1] = a[n-1];
    for(int i=n-2; i>=0; --i) max[i] = std::max(max[i+1], a[i]);

    if(k==2) {
        for(int i=1; i<n; ++i) {
            if(min[i-1] >= max[i]) {
                std::cout << "TAK\n" << i;
                return 0;
            }
        }
        std::cout << "NIE";
        return 0;
    }
    if(k==3) {
        if(max[1]<=a[0] || min[n-2]>=a[n-1]) {
            std::cout << "TAK\n" << 1 << ' ' << n-1;
            return 0;
        }
        for(int i=1; i<n-1; ++i) {
            if(a[i] >= max[i+1] || a[i] <= min[i-1]) {
               std::cout << "TAK\n" << i << ' ' << i+1;
               return 0;
            }
        }
        std::cout << "NIE";
        return 0;
    }
    
    std::vector<bool> przedzial(n-1);
    for(int i=0; i<k-1; ++i) przedzial[i] = true;

    if(a[n-1] <= a[n-2]) {
        if(!przedzial[n-2]) {
            przedzial[0] = false;
            przedzial[n-2] = true;
        }
        if(!przedzial[n-3]) {
            przedzial[1] = false;
            przedzial[n-3] = true;
        }
    }
    else if(a[0] < a[1]) {
        bool ok=false;
        for(int i=2; i<n-1; ++i) {
            if(a[i-1] < a[i]) continue;
            if(!przedzial[i-1]) {
                przedzial[0] = false;
                przedzial[i-1] = true;
                ok=true;
                break; 
            }
            if(!przedzial[i]) {
                przedzial[n-2] = false;
                przedzial[i] = true;
                ok=true;
                break;
            }
        }
        if(!ok) {
            std::cout << "NIE";
            return 0;
        }
    } 

    std::cout << "TAK\n";
    for(int i=0; i<n-1; ++i) {
        if(przedzial[i]) std::cout << i+1 << ' ';
    }

    return 0;
}