#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[300]; vector <int> v[300]; 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]; } return 1; } void add (int idx, int val) { idx %= m; 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) { idx %= m; 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 % 200 == 0) refresh (); } int cnt = 0, st = first; while (true) { cnt ++; st = nex[st]; if (st == first) break; } give_answer (cnt); }