#include "bartender.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
namespace {
lint encode(vector<int> v){
lint tot = 0;
int cnt = 0;
for(int i=0; i<sz(v); i++){
int rk = 0;
for(int j=0; j<i; j++){
if(v[j] < v[i]) rk++;
}
cnt++;
tot = tot * cnt + rk;
}
return tot;
}
vector<int> decode(lint w, int n){
vector<int> v(n);
vector<int> lst(n);
iota(lst.begin(), lst.end(), 1);
for(int i=n-1; i>=0; i--){
int md = w % (i + 1);
w /= i + 1;
v[i] = lst[md];
lst.erase(lst.begin() + md);
}
return v;
}
}
std::vector<int> BlendWines(int K, std::vector<int> R){
int N = R.size();
vector<int> tmp;
for(int i=0; i<N; i++){
if(R[i] > 12) tmp.push_back(R[i] - 12);
}
lint tot = encode(tmp);
vector<int> ans(N);
for(int i=0; i<N; i++){
if(R[i] <= 12) ans[i] = 1 + (tot >> (R[i] - 1)) % 2;
}
tot >>= 12;
for(int i=0; i<N; i++){
if(R[i] > 12){
ans[i] = 3 + (tot % 5);
tot /= 5;
}
}
return ans;
}
#include "taster.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
namespace {
lint encode(vector<int> v){
lint tot = 0;
int cnt = 0;
for(int i=0; i<sz(v); i++){
int rk = 0;
for(int j=0; j<i; j++){
if(v[j] < v[i]) rk++;
}
cnt++;
tot = tot * cnt + rk;
}
return tot;
}
vector<int> decode(lint w, int n){
vector<int> v(n);
vector<int> lst(n);
iota(lst.begin(), lst.end(), 1);
for(int i=n-1; i>=0; i--){
int md = w % (i + 1);
w /= i + 1;
v[i] = lst[md];
lst.erase(lst.begin() + md);
}
return v;
}
}
vector<int> mis(vector<int> v){
if(sz(v) <= 1) return v;
vector<int> LO, HI;
for(int i=0; i+1<sz(v); i+=2){
if(Compare(v[i], v[i + 1]) > 0) swap(v[i], v[i + 1]);
LO.push_back(v[i]);
HI.push_back(v[i + 1]);
}
if(sz(v) & 1) LO.push_back(v.back());
HI = mis(HI);
auto find_match_index = [&](int x){
int pos = find(v.begin(), v.end(), x) - v.begin();
pos ^= 1;
if(pos >= sz(v)) return 987654321;
int ret = find(HI.begin(), HI.end(), v[pos]) - HI.begin();
return ret;
};
sort(LO.begin(), LO.end(), [&](const int &a, const int &b){
return find_match_index(a) < find_match_index(b);
});
HI.insert(HI.begin(), LO[0]);
LO.erase(LO.begin());
for(auto i : {1, 0, 3, 2, 5, 4}){
if(i >= sz(LO)) continue;
int thres = find_match_index(LO[i]);
thres = min(thres, sz(HI));
int s = 0, e = thres;
while(s != e){
int m = (s+e)/2;
if(Compare(HI[m], LO[i]) > 0) e = m;
else s = m + 1;
}
HI.insert(HI.begin() + s, LO[i]);
}
return HI;
}
vector<int> get_order(vector<int> pos, int n){
pos = mis(pos);
vector<int> dap(n);
for(int i=0; i<sz(pos); i++) dap[pos[i]] = i + 1;
return dap;
}
std::vector<int> SortWines(int K, std::vector<int> A) {
int N = sz(A);
lint tot = 0;
for(int i=N-1; i>=0; i--){
if(A[i] > 2){
tot = tot * 5 + (A[i] - 3);
}
}
tot <<= 12;
vector<int> find_ord;
for(int i=0; i<N; i++){
if(A[i] <= 2){
find_ord.push_back(i);
}
}
vector<int> ord = get_order(find_ord, N);
vector<int> ans(N);
for(int i=0; i<N; i++){
if(A[i] <= 2){
ans[i] = ord[i];
if(A[i] == 2) tot += (1 << (ord[i] - 1));
}
}
if(N > 12){
auto dec = decode(tot, N - 12);
reverse(dec.begin(), dec.end());
for(int i=0; i<N; i++){
if(A[i] > 2){
ans[i] = dec.back() + 12;
dec.pop_back();
}
}
}
return ans;
}
