#include <iostream>
#include <queue>
#include <bitset>
#include <stack>
#include <vector>
#include <trilib.h>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#define prime first
#define alpha second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn = 1e5 + 100;
int first = 1;
/*
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;
}
*/
vector <int> v;
int pre[maxn], nex[maxn];
void remove (int fi, int mid, int se) {
pre[se] = fi;
nex[fi] = se;
first = fi;
}
void insert (int fi, int mid, int se) {
nex[fi] = mid;
nex[mid] = se;
pre[se] = mid;
pre[mid] = fi;
}
void refresh () {
v.clear();
int st = first;
while (true) {
v.PB (st);
st = nex[st];
if (st == first)
break;
}
}
int main() {
ios::sync_with_stdio(false);
int n = get_n ();
if (is_clockwise (1, 2, 3)) {
v.PB (1);
v.PB (2);
v.PB (3);
nex[1] = 2;
nex[2] = 3;
nex[3] = 1;
pre[1] = 3;
pre[2] = 1;
pre[3] = 2;
}
else {
v.PB (1);
v.PB (3);
v.PB (2);
nex[1] = 3;
nex[3] = 2;
nex[2] = 1;
pre[1] = 2;
pre[2] = 3;
pre[3] = 1;
}
for (int i = 4; i <= n; i++) {
int lo = 0, hi = v.size();
while (hi - lo > 1) {
int mid = (hi + lo) / 2;
if (is_clockwise (v[lo], v[mid], i))
lo = mid;
else
hi = mid;
}
int m = v.size();
if (!is_clockwise (v[lo], v[hi], i))
insert (v[lo], i, v[hi % m]);
else
continue;
while (!is_clockwise (i, nex[i], nex[nex[i]]))
remove (i, nex[i], nex[nex[i]]);
while (!is_clockwise (pre[pre[i]], pre[i], i))
remove (pre[pre[i]], pre[i], i);
refresh ();
}
give_answer (v.size());
}
