#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, a[N], b[N];
int cnt = 0;
vector<int> er(vector<int> a, int x){
vector<int> b;
for(auto it : a) if(it != x) b.pb(it);
return b;
}
/*
int Query(int x, int y){
cnt++;
if(b[x] < (b[y] - 1)) return 0;
if(b[x] == (b[y] + 1)) return 0;
return 1;
}*/
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
temp = (temp + (r - l + 1)) % (r - l + 1);
return temp + l;
}
int deg[N];
map<ii, bool> mp;
void solve_brute(vector<int> x, int l, int r){
assert(x.size() == (r - l + 1));
if(x.size() == 1){
a[x[0]] = l;
return;
}
assert(x.size() != 3);
for(int i = 0; i < x.size(); i++) deg[x[i]] = 0;
for(int i = 0; i < x.size(); i++){
for(int j = i + 1; j < x.size(); j++){
mp[{x[i], x[j]}] = Query(x[i], x[j]);
if(mp[{x[i], x[j]}]) deg[x[i]]++;
else deg[x[j]]++;
}
}
if(x.size() == 2){
if(!mp[{x[0], x[1]}]){
a[x[0]] = r, a[x[1]] = l;
}
else{
a[x[1]] = r, a[x[0]] = l;
}
return;
}
int mn0 = -1, mn1, mx0 = -1, mx1;
//cout << x.size() << "\n";
for(auto it : x){
if(deg[it] >= 2 && deg[it] <= x.size() - 3){
a[it] = l + deg[it];
}
if(deg[it] == 1){
if(mn0 == -1) mn0 = it;
else mn1 = it;
}
if(deg[it] == x.size() - 2){
if(mx0 == -1) mx0 = it;
else mx1 = it;
}
//cout << deg[it] << " ";
}
//cout << "\n";
//for(auto it : x) cout << b[it] << " ";
//cout << "\n";
if(min({mn0, mn1, mx0, mx1}) < 0) exit(0);
//cout << mn0 << " " << mn1 << "\n";
if(mp[{mn0, mn1}]){
a[mn0] = l; a[mn1] = l + 1;
}
else{
a[mn0] = l + 1; a[mn1] = l;
}
if(mp[{mx0, mx1}]){
a[mx0] = r - 1; a[mx1] = r;
}
else{
a[mx0] = r; a[mx1] = r - 1;
}
}
void solve(vector<int> x, int l, int r){
//for(auto it : x) assert(b[it] >= l && b[it] <= r);
shuffle(x.begin(), x.end(), default_random_engine(10));
if(x.size() <= 10){
solve_brute(x, l, r);
return;
}
int temp;
vector<int> vc1, vc2;
int iter = 0;
while(1){
iter++;
temp = x[rnd(0, x.size() - 1)];
int cnt1 = 0, cnt2 = 0;
for(int i = 0; (cnt1 + cnt2) < 10; i++){
if(temp == x[i]) continue;
if(Query(temp, x[i])) cnt1++;
else cnt2++;
}
if(cnt1 < 2 || cnt2 < 2) continue;
break;
}
//cout << temp << "\n";
for(auto it : x){
if(it == temp) continue;
if(Query(temp, it)) vc1.pb(it);
else vc2.pb(it);
}
//cout << vc1.size() << " " << vc2.size() << "\n";
//cout << temp << " " << l + vc1.size() << "\n";
a[temp] = l + vc1.size();
int w1 = vc1[0], w2 = vc2[0];
for(auto it : vc1){
if(it == w1) continue;
if(Query(it, w1)) w1 = it;
}
for(auto it : vc2){
if(it == w2) continue;
if(Query(w2, it)) w2 = it;
}
bool ck1 = 0, ck2 = 0;
a[w1] = l + vc1.size() + 1;
a[w2] = l + vc1.size() - 1;
vc1 = er(vc1, w1);
vc2 = er(vc2, w2);
//vc1 = er(vc1, w1);
//vc2 = er(vc2, w2);
if(vc1.size() == 3) vc1.pb(w2);
if(vc2.size() == 3) vc2.pb(w1);
solve(vc1, l, l + vc1.size() - 1);
solve(vc2, r - vc2.size() + 1, r);
}
/*
void solve(vector<int> x, int l, int r){
if(x.size() <= 4){
solve_brute(x, l, r);
return;
}
int temp;
vector<int> vc1, vc2;
while(1){
temp = x[rnd(0, x.size() - 1)];
vc1.clear(), vc2.clear();
for(auto it : x){
if(it == temp) continue;
if(!Query(it, temp)) vc1.pb(it);
else vc2.pb(it);
}
assert(vc1.size() && vc2.size());
if(vc1.size() == 1 || vc2.size() == 1) continue;
if(vc1.size() == 4 || vc2.size() == 4) continue;
break;
}
//cout << temp << " " << l + vc1.size() << "\n";
a[temp] = l + vc1.size();
int w1 = vc1[0], w2 = vc2[0];
for(auto it : vc1){
if(it == w1) continue;
if(Query(it, w1)) w1 = it;
}
for(auto it : vc2){
if(it == w2) continue;
if(Query(w2, it)) w2 = it;
}
bool ck1 = 0, ck2 = 0;
a[w1] = l + vc1.size() + 1;
a[w2] = l + vc1.size() - 1;
vc1 = er(vc1, w1);
vc2 = er(vc2, w2);
solve(vc1, l, l + vc1.size() - 1);
solve(vc2, r - vc2.size() + 1, r);
}*/
vector<int> Solve(int _n){
n = _n;
vector<int> temp;
for(int i = 0; i < n; i++) temp.pb(i);
solve(temp, 0, n - 1);
//solve_brute(temp, 0, n - 1);
vector<int> temp2;
for(int i = 0; i < n; i++) temp2.pb(a[i]);
return temp2;
}
/*
void process(int t){
int n = 1000;
for(int i = 0; i < n; i++) b[i] = i;
shuffle(b, b + n, default_random_engine(rnd(1, 10000)));
Solve(n);
cout << cnt << "\n";
//for(int i = 0; i < n; i++) cout << a[i] << " " << b[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
for(int i = 1; i <= t; i++) process(i);
cout << fixed << setprecision(10) << (double)cnt / (double)t << "\n";
}
*/
