#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
std::vector<int> BlendWines(int K, std::vector<int> a){
int N = a.size();
int G=min(N,12);
vector<int> s;
for(int i=0;i<N;++i)
if(a[i]>G)
s.pb(a[i]-G);
__int128 p=0;
//encode this shit
for(int j=0;j<s.size();++j)
{
int w=0;
for(int k=0;k<j;++k)
w+=s[k]<s[j];
p=p*(j+1)+w;
}
vector<int> o(N);
for(int i=0;i<N;++i)
{
int u=2;
if(a[i]>G) u=5;
int x=p%u; p/=u;
if(a[i]>G)
o[i]=x+3;
else o[i]=x+1;
}
assert(p==0);
return o;
}
#include "taster.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
map<pii,int> sb;
int query(int p,int q)
{
if(p>q) return !query(q,p);
if(sb.count(pii(p,q)))
return sb[pii(p,q)];
return sb[pii(p,q)]=(Compare(p,q)==-1);
}
void sort(std::vector<int> &v) {
if (v.size() == 1)
return;
std::vector<int> t;
std::map<int, int> m;
for (size_t i = 1; i < v.size(); i += 2) {
if (!query(v[i - 1], v[i]))
std::swap(v[i - 1], v[i]);
t.push_back(v[i]), m[v[i]] = v[i - 1];
}
sort(t);
int ex = v.size() & 1 ? v.back() : -1;
v = t;
v.insert(v.begin(), m[t[0]]);
for (size_t p = 4, l = 1, r = 3; l < t.size(); p <<= 1, l = r, r = p - r)
for (size_t i = std::min(r, t.size()) - 1, j = std::min(p, v.size()) - 1; i >= l; --i) {
while (v[j] != t[i]) --j;
v.insert(std::lower_bound(v.begin(), v.begin() + j, m[t[i]], query), m[t[i]]);
}
if (ex != -1)
v.insert(std::lower_bound(v.begin(), v.end(), ex, query), ex);
}
//optimal sort end
#define pb push_back
#define SZ 666666
bool big[SZ];
int g[SZ],c[SZ];
std::vector<int> SortWines(int K, std::vector<int> o) {
srand(123111111+__TIME__[7]*10000+__TIME__[6]*100
+__TIME__[5]*11231+__TIME__[4]*1231+__TIME__[3]*123132
+__TIME__[2]*12111+__TIME__[1]*11111+time(0));
int N = o.size();
vector<int> a(N);
int G=min(N,12);
__int128 p=0;
for(int i=N-1;i>=0;--i)
{
int u,x;
if(o[i]>=3)
big[i]=1,u=5,x=o[i]-3;
else u=2,x=o[i]-1;
p=p*u+x;
}
#ifdef LOCAL
cerr<<(long long)p<<"\n";
#endif
for(int i=N-G-1;i>=0;--i)
{
g[i]=p%(i+1); p/=i+1;
}
for(int i=0;i<=N-G-1;++i)
{
c[i]=g[i];
for(int j=0;j<i;++j)
if(c[j]>=g[i]) ++c[j];
}
int oo=0;
for(int i=0;i<N;++i)
if(big[i]) a[i]=c[oo++]+G+1;
vector<int> S;
for(int i=0;i<N;++i)
if(!big[i]) S.pb(i);
random_shuffle(S.begin(),S.end());
sort(S);
for(int i=0;i<S.size();++i)
a[S[i]]=i+1;
#ifdef LOCAL
for(auto t:o)
cout<<t<<",";
cout<<"\n";
for(auto t:a)
cout<<t<<",";
cout<<"\n";
#endif
return a;
}
