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 <cstdio>
#include <algorithm>

int data[500 * 1000];
int maxes[500 * 1000];

void load_data(int n) {
    for (int i = 0; i < n; i++) {
        scanf("%d", &data[i]);
    }
}

void solve_large(int n, int k) {
    int bad_position = -1;
    for (int i = 1; i < n; i++) {
        if (data[i - 1] >= data[i]) {
            bad_position = i;
            break;
        }
    }

    if (bad_position == -1) {
        // The sequence is strictly increasing, so it's not possible
        // to split into a valid sequence of intervals.
        puts("NIE");
        return;
    }

    // Choose a sequence of intervals such that the two consecutive elements
    // that are not increasing are placed in separate intervals.
    int start_position = std::min(std::max(0, bad_position - 2), n - k);
    puts("TAK");
    for (int i = 1; i < k; i++) {
        if (i > 1) {
            putchar(' ');
        }
        printf("%d", start_position + i);
    }
    putchar('\n');
}

void solve_3(int n) {
    int left_min = data[0];
    for (int i = 1; i < n - 1; i++) {
        if (left_min >= data[i]) {
            printf("TAK\n%d %d\n", i, i + 1);
            return;
        }
        left_min = std::min(left_min, data[i]);
    }

    int right_max = data[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        if (data[i] >= right_max) {
            printf("TAK\n%d %d\n", i, i + 1);
            return;
        }
        right_max = std::max(right_max, data[i]);
    }

    puts("NIE");
}

void solve_2(int n) {
    maxes[n - 1] = data[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        maxes[i] = std::max(maxes[i + 1], data[i]);
    }

    int left_min = data[0];
    for (int i = 1; i < n; i++) {
        if (left_min >= maxes[i]) {
            printf("TAK\n%d\n", i);
            return;
        }
        left_min = std::min(left_min, data[i]);
    }

    puts("NIE");
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    load_data(n);

    if (k >= 4) {
        solve_large(n, k);
    } else if (k == 3) {
        solve_3(n);
    } else {
        // k == 2
        solve_2(n);
    }

    return 0;
}