#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#define lc (p<<1)
#define rc ((p<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
int P, N;
int K = 0;
vector<int> seg(4*100001+10, 0);
int upd(int p, int l, int r, int val, int layer) {
seg[p]+=1;
//cout<<seg[p]<<' '<<l<<' '<<r<<' '<<val<<' '<<layer<<endl;
if(seg[p] == (r - l + 1)) return layer;
if(val<=mid) return upd(lc, l, mid, val, layer+1);
else return upd(rc, mid+1, r, val, layer+1);
}
void p1() {
int cnt1 = 1, cnt2 = 1;
cout<<upd(1, 1, N, 1, 0)<<endl;
seg.assign(4*100001+10, 0);
for(int i = 0; i<N-1; i++) {
int idx;
cin>>idx;
idx++;
cout<<upd(1, 1, N, idx, 0)<<endl;
}
}
void p2() {
int g1 = -1, g2 = -1;
vector<int> nums(N+1);
K = upd(1, 1, N, 1, 0);
vector<vector<int>> pos(K+1);
for(int i=1; i<=N; i++) {
int in;
cin>>in;
nums[i] = in;
pos[in].push_back(i);
}
if(pos[0].size()) {cout<<pos[0][0]-1<<' '<<pos[0][0]-1<<endl; return;}
else if(pos[1].size()>1) {cout<<pos[1][0]-1<<' '<<pos[1][1]-1<<endl; return;}
int L = 1, R = N;
if(pos[1][0]<=(L+R)/2) L = (L+R)/2 + 1;
else R = (L+R)/2;
int layer = 2;
while(L+1<R) {
int m = (L+R)/2;
int iL = lower_bound(pos[layer].begin(), pos[layer].end(), L) - pos[layer].begin();
int iR = lower_bound(pos[layer].begin(), pos[layer].end(), m+1) - pos[layer].begin();
bool okL = (iL<pos[layer].size() && pos[layer][iL]<=m);
bool okR = (iR<pos[layer].size() && pos[layer][iR]<=R);
if(okL && okR) {
cout<<pos[layer][iL]-1<<' '<<pos[layer][iR]-1<<endl;
return;
}
else if(okL && !okR) {
L = m+1;
}
else {
R = m;
}
layer++;
}
cout<<L-1<<' '<<R-1<<endl;
}
int main() {
cin>>P>>N;
if(P==1) p1();
else p2();
}
/*
2 8
*/
