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
 99
100
101
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;

void solve2(vector<int>& t) {
	int n = t.size();

	vector<int> mn(n), mx(n);

	mn[0] = t[0];
	for(int i=1;i<n;i++)
		mn[i] = min(mn[i-1], t[i]);

	mx[n-1] = t[n-1];
	for(int i=n-2;i>=0;i--)
		mx[i] = max(mx[i+1], t[i]);

	for(int i=0;i<n-1;i++)
		if(mn[i] >= mx[i+1]) {
			cout << "TAK\n" << i+1 << "\n";
			return;
		}

	cout << "NIE\n";
}

void solve3(vector<int>& t) {
	int n = t.size();

	vector<int> mn(n), mx(n);

	mn[0] = t[0];
	for(int i=1;i<n;i++)
		mn[i] = min(mn[i-1], t[i]);

	mx[n-1] = t[n-1];
	for(int i=n-2;i>=0;i--)
		mx[i] = max(mx[i+1], t[i]);

	for(int i=1;i<n-1;i++)
		if(mn[i] >= t[i] || t[i] >= mx[i]) {
			cout << "TAK\n" << i << " " << i+1 << "\n";
			return;
		}

	cout << "NIE\n";
}

bool cnt[MAXN+1];
int cnt_siz = 0;

void insert(vector<int> t, int n) {
	for(int i : t)
		if(0 < i && i < n && !cnt[i])
			cnt[i] = true, cnt_siz++;
}

void solveBig(vector<int>& t, int k) {
	int n = t.size();

	int a = -1, b = -1;
	for(int i=0;i<n-1;i++)
		if(t[i] >= t[i+1]) {
			a = i;
			b = i+1;
			break;
		}

	if(a == -1) {
		cout << "NIE\n";
		return;
	}

	insert({a,a+1,b,b+1}, n);

	for(int i=1;i<=n-1 && cnt_siz < k-1;i++)
		insert({i}, n);

	cout << "TAK\n";
	for(int i=1;i<n;i++)
		if(cnt[i]) cout << i << " ";
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,k;
	cin >> n >> k;

	vector<int> t(n);
	for(int& i : t) cin >> i;

	if(k == 2) solve2(t);
	else if(k == 3) solve3(t);
	else solveBig(t,k);

	return 0;
}