#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i //return Index template std::enable_if_t,std::vector>longest_increasing_subsequence(const std::vector&a){ if(a.empty())return std::vector(); static constexpr T inf=std::numeric_limits::max(); int n=a.size(); std::vectordp(n,inf); std::vectorid(n,-1); std::vectorpre(n); for(int i=0;i1){ int mid=(l+r)/2; (dp[mid]res(sz); res[sz-1]=id[sz-1]; for(int i=sz-2;i>=0;i--)res[i]=pre[res[i+1]]; return res; } struct has_update_impl{ template static auto check(T&&x)->decltype(x.update(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_update:public decltype(has_update_impl::check(std::declval())){}; template inline constexpr bool has_update_v=has_update::value; struct has_push_impl{ template static auto check(T&&x)->decltype(x.push(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_push:public decltype(has_push_impl::check(std::declval())){}; template inline constexpr bool has_push_v=has_push::value; struct has_middle_impl{ template static auto check(T&&x)->decltype(x.middle,std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_middle:public decltype(has_middle_impl::check(std::declval())){}; template inline constexpr bool has_middle_v=has_middle::value; template void splay(T*nd){ if constexpr(has_push_v&&!no_push)nd->push(); while(nd->par){ T *p=nd->par; T *pp=p->par; if constexpr(has_push_v&&!no_push){ if(pp)pp->push(); p->push(); nd->push(); } if(p->left==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->left=p->right; if(pp->left)pp->left->par=pp; p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; p->right=pp; pp->par=p; if constexpr(has_update_v)pp->update(),p->update(),nd->update(); continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; pp->right=nd->left; if(pp->right)pp->right->par=pp; nd->left=pp; pp->par=nd; nd->right=p; p->par=nd; if constexpr(has_update_v)pp->update(),p->update(),nd->update(); continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; if constexpr(has_update_v)p->update(),nd->update(); break; } else if(p->right==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; pp->left=nd->right; if(pp->left)pp->left->par=pp; nd->left=p; p->par=nd; nd->right=pp; pp->par=nd; if constexpr(has_update_v)pp->update(),p->update(),nd->update(); continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->right=p->left; if(pp->right)pp->right->par=pp; p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; p->left=pp; pp->par=p; if constexpr(has_update_v)pp->update(),p->update(),nd->update(); continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; if constexpr(has_update_v)p->update(),nd->update(); break; } else break; } } template [[nodiscard]]T* near(T *nd,decltype(T::key)k){ while(true){ if(kkey){ if constexpr(has_push_v)nd->push(); if(nd->left)nd=nd->left; else{ splay(nd); return nd; } } else if(nd->key)nd->push(); if(nd->right)nd=nd->right; else{ splay(nd); return nd; } } else{ splay(nd); return nd; } } return nullptr; } template [[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){ while(true){ if constexpr(has_push_v)nd->push(); decltype(T::sz) lsz=nd->left?nd->left->sz:0; if(lsz==k)break; else if(kleft; else{ nd=nd->right; k-=1+lsz; } } splay(nd); return nd; } template [[nodiscard]]T* merge(T* l,T *r){ if(!l)return r; if(!r)return l; while(r->left){ if constexpr(has_push_v)r->push(); r=r->left; } if constexpr(has_push_v)r->push(); splay(r); r->left=l; l->par=r; if constexpr(has_update_v)r->update(); return r; } template [[nodiscard]]T* left_most(T*nd){ T nil; T *rnd=&nil; while(nd->left){ if constexpr(has_push_v)nd->push(); T *c=nd->left; if(!c->left){ rnd->left=nd; if constexpr(has_update_v||correct_parent)nd->par=rnd; rnd=rnd->left; nd=c; } else{ if constexpr(has_push_v)c->push(); nd->left=c->right; c->right=nd; if constexpr(has_update_v||correct_parent){ if(nd->left)nd->left->par=nd; nd->par=c; } if constexpr(has_update_v)nd->update(); if constexpr(has_update_v||correct_parent)c->par=rnd; rnd->left=c; nd=c->left; rnd=rnd->left; } } if constexpr(has_push_v)nd->push(); rnd->left=nd->right; nd->right=nil.left; nil.left=nil.right=nullptr; if constexpr(has_update_v||correct_parent){ if(rnd->left)rnd->left->par=rnd; if(nd->right)nd->right->par=nd; nd->par=nullptr; } if constexpr(has_update_v){ if(rnd!=&nil){ while(rnd){ rnd->update(); rnd=rnd->par; } } } return nd; } template [[nodiscard]]T* right_most(T*nd){ T nil; T *lnd=&nil; while(nd->right){ if constexpr(has_push_v)nd->push(); T *c=nd->right; if(!c->right){ lnd->right=nd; if constexpr(has_update_v||correct_parent)nd->par=lnd; lnd=lnd->right; nd=c; } else{ if constexpr(has_push_v)c->push(); nd->right=c->left; c->left=nd; if constexpr(has_update_v||correct_parent){ if(nd->right)nd->right->par=nd; nd->par=c; } if constexpr(has_update_v){ nd->update(); } if constexpr(has_update_v||correct_parent)c->par=lnd; lnd->right=c; nd=c->right; lnd=lnd->right; } } if constexpr(has_push_v)nd->push(); lnd->right=nd->left; nd->left=nil.right; nil.left=nil.right=nullptr; if constexpr(has_update_v||correct_parent){ if(lnd->right)lnd->right->par=lnd; if(nd->left)nd->left->par=nd; nd->par=nullptr; } if constexpr(has_update_v){ if(lnd!=&nil){ while(lnd){ lnd->update(); lnd=lnd->par; } } } return nd; } template std::vectormerge_insertion_sort(int n,const Compare&compare){ struct node{ node *left=nullptr,*right=nullptr,*par=nullptr; int key=-1; int sz=1; inline void update(){ sz=1; if(left)sz+=left->sz; if(right)sz+=right->sz; } }; auto dfs=[&](auto self,std::vector&idx)->void { int m=idx.size(); if(m==1)return; int amari=-1; if(m&1){ amari=idx.back(); m--; } std::vector>small; std::vectorlarge; small.reserve(m/2); large.reserve(m/2); for(int i=0;ipos(n,-1); for(int i=0;ismall_v(m/2+(amari!=-1)); for(const auto&[a,b]:small)small_v[pos[b]]=a; if(amari!=-1){ small_v.back()=amari; m++; } std::vectornds; nds.reserve(m); nds.resize(large.size()+1); nds[0].key=small_v[0]; node *root=&nds[0]; for(int i=0;i<(int)large.size();i++){ root->par=&nds[i+1]; nds[i+1].left=root; root=root->par; root->key=large[i]; root->update(); } for(int i=1,j=2,k=4;i<(int)small_v.size();i+=j,j=k-j,k<<=1){ for(int l=std::min(small_v.size(),i+j)-1;l>=i;l--){ int left=-1,right=std::min(root->sz,i*2+j-1); while(right-left>1){ int mid=(left+right)/2; root=get_k(root,mid); if(compare(root->key,small_v[l]))left=mid; else right=mid; } nds.emplace_back(); node *nd=&nds.back(); nd->key=small_v[l]; if(right==root->sz){ nd->left=root; root->par=nd; root=nd; root->update(); } else{ root=get_k(root,right); nd->left=root->left; if(nd->left)nd->left->par=nd; nd->update(); nd->par=root; root->left=nd; root->update(); } } } for(int i=0;ikey; if(i+1==m)break; node *nd=root->right; nd->par=nullptr; root->right=nullptr; root=nd; } }; std::vectorres(n); std::iota(res.begin(),res.end(),0); dfs(dfs,res); return res; } void SOLVE(){ int n; cin>>n; #ifdef LOCAL vectorp(n); cin>>p; #endif auto query=[&](vectora)->int { assert(a.size()==n); cout<<"?"; rep(i,a.size())cout<<' '<s(n); rep(i,n)s[i]=a[p[i]]; return longest_increasing_subsequence(s).size(); #else int res; cin>>res; return res; #endif }; int rv=[&](){ rep(i,n){ vectora(n); a[i]=-1; if(query(a)==1)return i; } return -1; }(); int lv=[&](){ rep(i,n){ vectora(n); a[i]=1; if(query(a)==1)return i; } return -1; }(); vectorord; rep(i,n)if(i!=lv&&i!=rv)ord.push_back(i); auto comp=[&](int lhs,int rhs)->bool { vectora(n,100); a[rv]=2; a[lv]=-1; a[lhs]=0; a[rhs]=1; return query(a)==4; }; if(n-2>0){ vectorord2=merge_insertion_sort(ord.size(),[&](int lhs,int rhs){ return comp(ord[lhs],ord[rhs]); }); vectorord3(ord.size()); rep(i,ord.size())ord3[i]=ord[ord2[i]]; ord=ord3; } debug(lv,rv); vectorans(n); ans[0]=lv; ans[n-1]=rv; rep(i,ord.size())ans[i+1]=ord[i]; cout<<'!'; rep(i,n)cout<<' '<