#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 long long inversion(const std::vector&a){ if(a.empty())return 0; std::vectorg[2]; g[0].resize(a.size()); g[1].resize(a.size()); long long res=0; auto dfs=[&](auto self,int l,int r,int k)->void { if(l+1==r)g[k][l]=a[l]; else{ int mid=(l+r)/2; self(self,l,mid,k^1); self(self,mid,r,k^1); int lp=l,rp=mid,p=l; while(lp long long inversion(const std::vector&a,const std::vector&b){ assert(a.size()==b.size()); int n=a.size(); std::vectorz(b); std::sort(z.begin(),z.end()),z.erase(std::unique(z.begin(),z.end()),z.end()); std::vectorzb(n); std::vectorcnt(z.size()); for(int i=0;icnt2(cnt); std::vectorord(n); for(int i=n-1;i>=0;i--)ord[--cnt[zb[i]]]=i; std::vectorza(n); for(int i=0;i #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct BinaryIndexedTree{ private: using S=typename M::S; std::vectordat; int z; public: BinaryIndexedTree(){} explicit BinaryIndexedTree(int n):z(ceil_pow2(n)),dat(n,M::e()){} explicit BinaryIndexedTree(const std::vector&init):z(ceil_pow2((int)init.size())),dat(init){ for(int i=0;i<(int)dat.size();i++){ int j=i+((i+1)&-(i+1)); if(j<(int)dat.size())dat[j]=M::op(dat[i],dat[j]); } } inline void add(int i,S x){ while(i<(int)dat.size()){ dat[i]=M::op(dat[i],x); i+=(i+1)&-(i+1); } } inline S sum(int i)const{ S res=M::e(); while(i>0){ res+=dat[i-1]; i-=i&-i; } return res; } inline S sum(int l,int r)const{ S lp=M::e(),rp=M::e(); while(l=1;i>>=1){ if(res+i<=(int)dat.size()&&dat[res+i-1] struct MonoidAdd{ using S=T; using F=std::nullptr_t; static inline S op(S x,S y){return x+y;} static inline S e(){return T();} static inline S mapping(F,const S&x,long long){return x;} static inline F composition(F,F){return nullptr;} static inline F id(){return nullptr;} static inline S inverse(S x){return -x;} static inline void revS(S&x){} static inline S pow(S x,long long p){return x*p;} }; void SOLVE(){ int n; cin>>n; #ifdef LOCAL vectora(n); cin>>a; #endif auto query=[&](int l,int r)->ll { cout<<"? "<({a.begin()+l,a.begin()+r}); #else cin>>res; #endif return res; }; BinaryIndexedTree>BIT(vector(n,1)); vectorqres(n); rep(i,n)qres[i]=query(0,i+1); vectorans(n); debug(qres); for(int i=n-1;i>=1;i--){ ll r=qres[i],l=qres[i-1]; ll diff=r-l; ll len=i+1; diff=len-diff-1; ll elem=BIT.lower_bound(diff+1); ans[i]=elem; debug(i,diff,elem); BIT.add(elem,-1); } rep(i,n)if(BIT.sum(i,i+1)==1)ans[0]=i; cout<<"!"; rep(i,n)cout<<' '<