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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 500005;

int n, k, tab[N], minn[N], maxx[N], i, j, c;
set<int> s;

int main() {
scanf("%d %d", &n, &k);
for (i=1;i<=n;i++) scanf("%d", &tab[i]);
maxx[n + 1] = 0;
for (i=n;i>=1;i--) maxx[i] = max(tab[i], maxx[i + 1]);
minn[0] = INF;
for (i=1;i<=n;i++) minn[i] = min(tab[i], minn[i - 1]);
if (k == 2) {	
	for (i=1;i<n;i++) if (minn[i] >= maxx[i + 1]) {
		printf("TAK\n%d\n", i);
		return 0;
	}
} else if (k >= 4) {
	s.clear();
	for (i=1;i<n;i++) if (tab[i] >= tab[i + 1]) {
		if (i > 1) s.insert(i - 1);
		s.insert(i);
		if (i < n - 1) s.insert(i + 1);
		for (j=1;j<n && s.size() < k - 1;j++) s.insert(j);
		printf("TAK\n", i);
		for (auto& w : s) printf("%d ", w);
		printf("\n");
		return 0;
	}
} else {
	c = n + 1;
	for (i=2;i<=n;i++) if (tab[i] == minn[n]) c = min(c, i);
	for (i=1;i<n;i++) if (tab[i] == maxx[1]) c = min(c, i);
	if (c != n + 1) {
		s.clear();
		if (c > 1) s.insert(c - 1);
		if (c < n) s.insert(c);
		for (j=1;j<n && s.size() < k - 1;j++) s.insert(j);
		printf("TAK\n", i);
		for (auto& w : s) printf("%d ", w);
		printf("\n");
		return 0;
	}
	
}
printf("NIE\n");
return 0;
}