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
#include <bits/stdc++.h>
using namespace std;
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k;
	cin >> n >> k; k --;
	vector<int> a(n), use(n - 1);
	for(int i = 0; i < n; i ++) cin >> a[i];
	vector<int> mn(n), mx(n);
	auto check2 = [&] {
		mn[0] = a[0];
		for(int i = 1; i < n; i ++) mn[i] = min(a[i], mn[i - 1]);
		mx[n - 1] = a[n - 1];
		for(int i = n - 2; i >= 0; i --) mx[i] = max(a[i], mx[i + 1]);
		for(int i = 0; i < n - 1; i ++) if(mn[i] >= mx[i + 1]) return use[i] = 1, true;
		return false;
	};
	auto check3 = [&] {
		int p = find(a.begin(), a.end(), mx[0]) - a.begin();
		if(p != n - 1) return use[p] = use[p - 1] = 1, true;
		int q = find(a.rbegin(), a.rend(), mn.back()) - a.rbegin();
		q = n - 1 - q;
		if(q) return use[p] = use[p - 1] = 1, true;
		return false;
	};
	auto check4 = [&] {
		for(int i = 1; i < n; i ++) if(a[i] <= a[i - 1]) {
			return use[i - 2] = use[i - 1] = use[i] = 1, true;
		}
		return false;
	};
	if(!check2() && !check3() && !check4()) {
		cout << "NIE\n";
		return 0;
	}
	int cnt = accumulate(use.begin(), use.end(), 0);
	if(cnt > k) {
		cout << "NIE\n";
	} else {
		for(int i = 0; i < n - 1; i ++) if(!use[i] && cnt < k) use[i] = 1, cnt ++;
		assert(cnt == k);
		cout << "TAK\n";
		for(int i = 0; i < n - 1; i ++) if(use[i]) cout << i + 1 << ' ';
		cout << '\n';
	}
	return 0;
}