#include "koala.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int minValue(int N, int W) {
int B[N], R[N];
rep(i, N) B[i] = 0;
B[0] = 1;
playRound(B, R);
rep(i, N) if (R[i] <= B[i]) return i;
abort();
}
int maxValue(int N, int W) {
return 0;
}
int greaterValue(int N, int W) {
return 0;
}
int N, W;
tuple<int,int,int> dp[201];
int simulation(vector<int> cost, int l, int r) {
rep(i, W+1) dp[i] = make_tuple(0, 0, 0);
rep(i, N) {
assert(cost[i] > 0);
for (int j=W-cost[i]; j>=0; j--) {
dp[j+cost[i]] = max(dp[j+cost[i]], make_tuple(get<0>(dp[j])+(i+1), get<1>(dp[j])+1, get<2>(dp[j])-(l<=i+1&&i+1<=r)));
}
}
int lo = -get<2>(dp[W]);
rep(i, W+1) dp[i] = make_tuple(0, 0, 0);
rep(i, N) {
assert(cost[i] > 0);
for (int j=W-cost[i]; j>=0; j--) {
dp[j+cost[i]] = max(dp[j+cost[i]], make_tuple(get<0>(dp[j])+(i+1), get<1>(dp[j])+1, get<2>(dp[j])+(l<=i+1&&i+1<=r)));
}
}
int hi = get<2>(dp[W]);
assert(lo==hi);
return lo;
}
int perm[100];
void solve(int l, int r, vector<int> set) {
assert(r-l+1 == set.size());
assert(l<=r);
//cout<<"["<<l<<","<<r<<"] {";for(int x: set)cout<<x<<",";cout<<"}\n";
if (l == r) {
perm[set[0]] = l;
return;
}
pair<int, P> mp = make_pair(INF, P(-1, -1));
for (int outside=1; outside<=100; outside++) {
for (int k=2; k<=100; k++) {
//if (outside == k) continue;
if ((outside-1)*(N-(r-l+1)) + (k-1)*(r-l+1) > W) continue;
vector<int> cost(N);
for (int i=1; i<=N; i++) {
if (l <= i && i <= r) cost[i-1] = k;
else cost[i-1] = outside;
}
int left = simulation(cost, l, r);
int right = (r-l+1)-left;
if (left==0||right==0)continue;
mp = min(mp, make_pair(abs(left-right), P(k, outside)));
}
}
int val = mp._2._1;
int outside = mp._2._2;
assert(val!=-1);
int B[100], R[100];
rep(i, N) B[i] = outside-1;
for (int i : set) B[i] = val-1;
playRound(B, R);
vector<int> left, right;
for (int i : set) {
if (R[i] >= val) right.pb(i);
else left.pb(i);
}
solve(l, l+left.size()-1, left);
solve(l+left.size(), r, right);
}
void allValues(int NN, int WW, int *P) {
N = NN, W = WW;
if (W == 2*N) {
}
else {
}
vector<int> left, right;
rep(i, N) perm[i] = -1;
vector<int> all;
rep(i, N) all.pb(i);
solve(1, N, all);
rep(i, N) P[i] = perm[i];
}
