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

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	int a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	if(k>=4){
		int loc = -1;
		for(int i = 0; i < n-1; i++){
			if(a[i]>=a[i+1]){
				loc=i;
			}
		}
		if(loc == -1) cout << "NIE";
		else{
			int ctr = 0, ctr2 = 0;
			cout << "TAK\n";
			for(int i = 0 ;ctr<k-4; i++){
				cout << i+1 << ' ';
				if(i!=loc&&i!=loc-1&&i!=loc+1) ctr++;
				else ctr2++;
			}
			for(int i = loc-1+ctr2; i <= loc+1; i++) cout << i+1 << ' ';
		}
	}else if(k==3){
		int sm=1e9+9, lg=-1;
		int sml=0, lgl=0;
		for(int i = 0; i < n; i++){
			if(sm>=a[i]){
				sml = i;
				sm=a[i];
			} 
			if(lg<a[i]){
				lgl = i;
				lg=a[i];
			} 
		}
	//	cout << lgl << ' '<< sml << '\n';
		if(sml!=0){
			cout << "TAK\n" << min(sml, n-2) << ' ' << min(sml, n-2)+1;
			return 0;
		}
		if(lgl!=n-1){
			cout << "TAK\n" << max(lgl, 1) << ' ' << max(lgl, 1)+1;
			return 0;
		}
		cout << "NIE";
	}else{
		int lg[n], sm[n];
		lg[n-1]=0; sm[0]=1e9;
		for(int i = 0; i < n; i++){
			sm[i]=min(sm[i], a[i]);
			if(i!=n-1) sm[i+1]=sm[i];
		}
		for(int i = n-1; i >= 0; i--){
			lg[i]=max(lg[i], a[i]);
			if(i!=0) lg[i-1]=lg[i];
		}
		for(int i = 0; i < n-1; i++){
			if(sm[i]>=lg[i+1]){
				cout << "TAK\n" << i+1;
				return 0;
			}
		}
		cout << "NIE";
	}
	return 0;
}