#include <bits/stdc++.h>
#include <trilib.h>
using namespace std;
const int maxn = 4e4 + 100;
const int SQRT = 3;
int first = 1, m = 3;
int pre[maxn], nex[maxn], nexsqrt[maxn];
/*
int get_n () {
int k;
cin >> k;
return k;
}
bool is_clockwise (int fi, int se, int th) {
cout << fi << " " << se << " " << th << endl;
bool k;
cin >> k;
return k;
}
void give_answer (int x) {
cout << x << endl;
}
void print_array () {
int tmp = first;
while (true) {
cout << tmp << " ";
tmp = nex[tmp];
if (tmp == first)
break;
}
cout << endl;
tmp = first;
while (true) {
cout << nexsqrt[tmp] << " ";
tmp = nex[tmp];
if (tmp == first)
break;
}
cout << endl << endl;
}
*/
void remove (int fi, int mid, int se) {
m --;
pre[se] = fi, nex[fi] = se;
// cout << "Remove " << fi << " " << mid << " " << se << endl;
int k = SQRT;
while (k --) {
if (nexsqrt[fi] != -1) {
nexsqrt[fi] = nex[nexsqrt[fi]];
if (nexsqrt[fi] == first)
nexsqrt[fi] = -1;
}
fi = pre[fi];
}
if (mid == first)
first = se;
}
void insert (int fi, int mid, int se) {
m ++;
// cout << "insert " << fi << " " << mid << " " << se << endl;
nex[fi] = mid, nex[mid] = se;
pre[se] = mid, pre[mid] = fi;
int k = SQRT;
nexsqrt[mid] = nexsqrt[fi];
while (k --) {
if (nexsqrt[fi] != -1)
nexsqrt[fi] = pre[nexsqrt[fi]];
if (k == 0)
nexsqrt[fi] = mid;
if (fi == first)
break;
fi = pre[fi];
}
if (m == SQRT + 1)
nexsqrt[first] = pre[first];
}
int get (int idx) {
idx %= m;
int tmp = first;
while (idx > 0) {
if (idx >= SQRT) {
tmp = nexsqrt[tmp];
idx -= SQRT;
}
else {
tmp = nex[tmp];
idx --;
}
}
return tmp;
}
void build_first () {
if (is_clockwise (1, 2, 3)) {
nex[1] = 2;
nex[2] = 3;
nex[3] = 1;
pre[1] = 3;
pre[2] = 1;
pre[3] = 2;
}
else {
nex[1] = 3;
nex[3] = 2;
nex[2] = 1;
pre[1] = 2;
pre[2] = 3;
pre[3] = 1;
}
}
int main() {
ios::sync_with_stdio(false);
memset (nexsqrt, -1, sizeof nexsqrt);
int n = get_n ();
build_first ();
for (int i = 4; i <= n; i++) {
int lo = 0, hi = m;
while (hi - lo > 1) {
int mid = (hi + lo) >> 1;
int x = get (lo), y = get (mid);
if (!is_clockwise (x, y, i))
hi = mid;
else
lo = mid;
}
int x = get (lo), y = get (hi);
if (is_clockwise (x, y, i))
continue;
insert (get (lo), i, get (hi));
// print_array ();
while (!is_clockwise (i, nex[i], nex[nex[i]])) {
remove (i, nex[i], nex[nex[i]]);
// print_array ();
}
while (!is_clockwise (pre[pre[i]], pre[i], i)) {
remove (pre[pre[i]], pre[i], i);
// print_array ();
}
}
give_answer (m);
}
