#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; } */ 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 (); } int m = v.size(); give_answer (m); }