//#define _CRT_SECURE_NO_WARNINGS
//#define test 0
//
//#include <algorithm>
//#include <utility>
//#include <vector>
//#include <cstdio>
//#include <iostream>
//#include <string>
//#include <time.h>
//#include <set>
//#include <cassert>
//
//#define forn(i, n) for (int i = 0; i < (n); i++)
//#define fornn(i, q, n) for (int i = (q); i < (n); i++)
//#define times clock() * 1.0 / CLOCKS_PER_SEC
//using namespace std;
//
//typedef long long ll;
//
//int solve();
//
//int main() {
//#ifdef _DEBUG
//	//freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
//#else
//	//freopen("video.in", "r", stdin), freopen("video.out", "w", stdout);
//#endif
//	solve();
//
//	return 0;
//}
//
//const int MAXN = 1e3 + 7;
//
//int n;
//string temp;
//int work = 1;
//int interact(int l, int r);
//int G[3007][3007];
//int it = 0;
//int ask(int pos1, int pos2) {
//	if (G[pos1][pos2] != 0) return G[pos1][pos2];
//	it++;
//	if (it == 72000) {
//		cout << 1 / 0;
//	}
//	cout << "?" << " " << pos1 + 1 << " " << pos2 + 1 << endl;
//	cout.flush();
//	int ans;
//	cin >> ans;
//
//	G[pos1][pos2] = ans;
//	return ans;
//}
//
//int solve() {
//	cin >> n;
//	int k = ask(0, n - 1);
//	vector<int> G(n);
//	int cur = 0;
//	int cpos = 0;
//	int mx = 0;
//	vector<pair<int, int> > pos;
//	while (cpos < n) {
//		int l = cpos, r = n;
//		while (r - l > 1) {
//			int m = (l + r) / 2;
//			if (ask(cpos, m) > 1) {
//				r = m;
//			}
//			else {
//				l = m;
//			}
//		}
//		mx = max(mx, cur + 1);
//		fornn(i, cpos, l + 1) {
//			G[i] = cur;
//		}
//		pos.push_back(make_pair(l, cur));
//		cpos = l + 1;
//	}
//	cout << "Ready!" << endl;
//	int tt = 0;
//	forn(i, n) {
//		tt = max(tt, G[i] + 1);
//	}
//	cout << tt << endl;
//	forn(i, n) {
//		cout << G[i] + 1 << " ";
//	}
//	cout << endl;
//	cout.flush();
//	return 0;
//}