#include "koala.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
int minValue(int N, int W) {
int B[N],R[N];
B[0] = 1;
for (int j = 1;j<N;j++) B[j] = 0;
playRound(B,R);
for (int j = 1;j<N;j++) {
if (!R[j]) return j;
}
B[1] = 1;
B[0] = 0;
playRound(B,R);
if (!R[0]) return 0;
for (int j = 1;j<N;j++) {
if (!R[j]) return j;
}
return -1;
}
int maxValue(int N, int W) {
assert(N == W && W == 100);
int B[N]{},R[N]{};
for (int i = 0;i<N;i++) B[i] = 1;
vi top50;
playRound(B,R);
for (int i = 0;i<N;i++) if (R[i] == 2) top50.push_back(i);
for (int i = 0;i<N;i++) B[i] = 0;
for (auto it : top50) B[it] = 2;
playRound(B,R);
vi top25;
for (int i = 0;i<N;i++) if (R[i] == 3) top25.push_back(i);
for (int i = 0;i<N;i++) B[i] = 0;
for (auto it : top25) B[it] = 4;
playRound(B,R);
vi top9;
for (int i = 0;i<N;i++) if (R[i] == 5) top9.push_back(i);
for (int i = 0;i<N;i++) B[i] = 0;
for (auto it : top9) B[it] = 11;
playRound(B,R);
for (int i = 0;i<N;i++) if (R[i] == 12) return i;
}
int greaterValue(int N, int W) {
int B[N]{},R[N];
int l = 1;
int r = min(9,N/2);
while (l<=r) {
int mid = (l+r) >> 1;
B[0] = B[1] = mid;
playRound(B,R);
if ((R[0] > mid) != (R[1] > mid)) return R[0] < R[1];
if (R[0] > mid) l = mid+1;
else r = mid-1;
}
}
int greaterValue2(int N,int a,int b) {
int B[N]{},R[N];
int l = 1;
int r = min(9,N/2);
while (l<=r) {
int mid = (l+r) >> 1;
B[a] = B[b] = mid;
playRound(B,R);
if ((R[a] > mid) != (R[b] > mid)) return R[a] < R[b];
if (R[a] > mid) l = mid+1;
else r = mid-1;
}
}
int greaterValue3(int N,int a,int b) {
int B[N]{},R[N];
B[a] = B[b] = N-1;
playRound(B,R);
if (R[a] > N-1) return 0;
return 1;
}
void mergesort1(int* P,int l,int r,const int N) {
if (l == r) {
P[l] = 1;
return;
}
int m = (l+r) >> 1;
mergesort1(P,l,m,N);
mergesort1(P,m+1,r,N);
vector<pii> sol,sag;
for (int j = l;j<=m;j++) sol.push_back({P[j],j});
for (int j = m+1;j<=r;j++) sag.push_back({P[j],j});
sort(all(sol)),sort(all(sag));
int ctr = 1;
int ptr1 = 0,ptr2 = 0;
while (ptr1 != big(sol) || ptr2 != big(sag)) {
if (ptr1 == big(sol)) P[sag[ptr2++].ss] = ctr++;
else if (ptr2 == big(sag)) P[sol[ptr1++].ss] = ctr++;
else {
if (greaterValue3(N,sol[ptr1].ss,sag[ptr2].ss)) P[sol[ptr1++].ss] = ctr++;
else P[sag[ptr2++].ss] = ctr++;
}
}
}
int nn;
int rooty(int x) {
for (int i = nn-1;i>=1;i--) {
if (i*i<=x) return i;
}
}
void dnq(int* P,vi& pos,int l,int r) {
if (l == r) {
assert(big(pos) == 1);
P[pos[0]] = l;
return;
}
int splitshit = min(nn/(r-l+1),rooty(2*l));
int B[nn]{},R[nn];
for (auto it : pos) B[it] = splitshit;
playRound(B,R);
vi great,smal;
for (auto it : pos) {
if (R[it] > splitshit) great.push_back(it);
else smal.push_back(it);
}
dnq(P,smal,l,l+big(smal)-1);
dnq(P,great,l+big(smal),r);
}
void allValues(int N, int W, int *P) {
nn = N;
if (W == 2*N) mergesort1(P,0,N-1,N);
else {
vi pos;
for (int j = 0;j<N;j++) pos.push_back(j);
dnq(P,pos,1,N);
}
}
