#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); }