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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
int mx,mn,mnp[500007],mxp[500007],mxs[500007],a,n,k,pom1,mxsp[500007];
vector<int>t;
int main()
{
	cin>>n>>k;
	mn=1000000007;
	for(int i=0; i<n; i++)
	{
		cin>>a;
		t.push_back(a);
		mxp[i]=max(mx,a);
		mx=mxp[i];
		mnp[i]=min(mn,a);
		mn=mnp[i];
	}
	mx=0;
	for(int i=n-1; i>=0; i--)
	{
		mxs[i]=max(t[i],mx);
		mx=mxs[i];
	}
	if(k>=3)
	{
		int pom=0;
		while(t[pom]<mx)
		{
			pom++;
		}
		//cout<<pom<<" "<<mx<<"\n";
		if(pom<n-1)
		{
			cout<<"TAK\n";
			for(int i=1; i<k-2; i++)
			{
				if(pom+1==i||pom==i)
				{
					k++;
				}
				cout<<i<<" ";
			}
			if(k-2<=pom+1)
			{
				if(pom>0)
				{
					cout<<pom<<" "<<pom+1<<"\n";
					return 0;
				}
				else
				{
					cout<<pom+1<<" "<<pom+2<<"\n";
					return 0;
				}
			}
			else
			{
				cout<<"\n";
				return 0;
			}
			return 0;
		}
		else
		{
			while(t[pom]==mxp[pom]&&pom>0&&mxp[pom-1]!=mxp[pom])
			{
				pom--;
			}
			if(pom==0)
			{
				cout<<"NIE\n";
				return 0;
			}
			else
			{
				pom1=0;
				while(t[pom1]<mxp[pom])
				{
					pom1++;
				}
				if(k>3)
				{
					cout<<"TAK\n";
					for(int i=1; i<k-3; i++)
					{
						if(pom1+1==i||pom1==i||pom+1==i)
						{
							k++;
						}
						cout<<i<<" ";
					}
					if(k-4<pom1)
					{
						cout<<pom1<<" ";
					}
					if(k-4<pom1+1)
					{
						cout<<pom1+1<<" ";
					}
					if(k-4<pom+1)
					{
						cout<<pom+1<<" ";
					}
					cout<<"\n";
					return 0;
				}
				else
				{
					mx=0;
					for(int i=pom; i>=0; i--)
					{
						mxsp[i]=max(mx,t[i]);
						mx=mxsp[i];
					}
					for(int i=0; i<pom; i++)
					{
						if(mnp[i]>=mxsp[i+1])
						{
							cout<<"TAK\n";
							cout<<i+1<<" "<<pom+1<<"\n";
							return 0;
						}
					}
					cout<<"NIE\n";
					return 0;
				}
			}
		}
	}
	else
	{
		for(int i=0; i<n-1; i++)
		{//cout<<"i="<<i<<" "<<mnp[i]<<" "<<mxs[i+1]<<"\n";
			if(mnp[i]>=mxs[i+1])
			{
				cout<<"TAK\n";
				cout<<i+1<<"\n";
				return 0;
			}
		}
	}
	cout<<"NIE\n";
}