#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 = 4e4 + 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;
}
*/
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;
}
int m = 3;
const int blocks = 210;
int ted[blocks + 10];
vector <int> v[blocks];
int get (int idx) {
idx %= m;
int cnt = 0;
for (int i = 0; i < blocks; i++) {
if (cnt <= idx and cnt + ted[i] > idx) {
for (auto w : v[i]) {
if (cnt == idx)
return w;
cnt ++;
}
}
cnt += ted[i];
}
}
void add (int idx, int val) {
m++;
int cnt = 0;
for (int i = 0; i < blocks; i++) {
if (cnt <= idx and cnt + ted[i] > idx) {
ted[i] ++;
vector <int> g = v[i];
v[i].clear();
for (auto w : g) {
if (cnt == idx) {
cnt ++;
v[i].PB (w);
v[i].PB (val);
continue;
}
v[i].PB (w);
cnt ++;
}
return;
}
}
}
void del (int idx) {
m --;
int cnt = 0;
for (int i = 0; i < blocks; i++) {
if (cnt <= idx and cnt + ted[i] > idx) {
ted[i] --;
vector <int> g = v[i];
v[i].clear();
for (auto w : g) {
if (cnt == idx) {
cnt ++;
continue;
}
v[i].PB (w);
cnt ++;
}
return;
}
cnt += ted[i];
}
}
int a[maxn];
void refresh () {
int tmp = 0;
for (int i = 0; i < blocks; i++)
for (auto w : v[i])
a[tmp ++] = w;
for (int i = 0; i < blocks; i++) {
v[i].clear();
ted[i] = 0;
}
int k = 0;
for (int i = 0; i < tmp; i++) {
ted[k] ++;
v[k].PB (a[i]);
if (i % blocks == 0)
k ++;
}
}
int main() {
ios::sync_with_stdio(false);
int n = get_n ();
if (is_clockwise (1, 2, 3)) {
nex[1] = 2;
nex[2] = 3;
nex[3] = 1;
pre[1] = 3;
pre[2] = 1;
pre[3] = 2;
v[0].PB (1);
v[0].PB (2);
v[0].PB (3);
}
else {
nex[1] = 3;
nex[3] = 2;
nex[2] = 1;
pre[1] = 2;
pre[2] = 3;
pre[3] = 1;
v[0].PB (1);
v[0].PB (3);
v[0].PB (2);
}
ted[0] = 3;
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));
add (lo, i);
int idx = lo + 1;
while (!is_clockwise (i, nex[i], nex[nex[i]])) {
remove (i, nex[i], nex[nex[i]]);
del (idx + 1);
}
while (!is_clockwise (pre[pre[i]], pre[i], i)) {
remove (pre[pre[i]], pre[i], i);
if (idx > 0) {
del (idx - 1);
idx --;
}
else {
del (m - 1);
}
}
if (i % 300 == 0)
refresh ();
}
int cnt = 0, st = first;
while (true) {
cnt ++;
st = nex[st];
if (st == first)
break;
}
give_answer (cnt);
}
