// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2") #include using namespace std; #include using namespace atcoder; // #include // using namespace boost::multiprecision; #define ll long long #define ld long double #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define vi vector #define vl vector #define vd vector #define vb vector #define vs vector #define vc vector #define ull unsigned long long #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() template inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } // #define ll int // #define ll int128_t // #define ll int256_t // #define ll cpp_int constexpr ll inf = (1ll << 62); // constexpr ll inf = (1 << 30); // const double PI=3.1415926535897932384626433832795028841971; // uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123; // inline uint32_t xor_next() { // uint32_t t = xor_x ^ (xor_x << 11); // xor_x = xor_y; xor_y = xor_z; xor_z = xor_w; // return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8)); // } // inline int rnd(int max_val) { return xor_next() % max_val; } struct Timer { std::chrono::steady_clock::time_point start_time; Timer() { reset(); } // 測定の起点リセット用 void reset() { start_time = std::chrono::steady_clock::now(); } // スタートからの経過時間をミリ秒(msec)で返す long long get_ms() const { auto now = std::chrono::steady_clock::now(); return std::chrono::duration_cast(now - start_time).count(); } }; // ll rui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a*rui(a*a,b/2); // return rui(a*a,b/2); // } // vl fact; // ll kai(ll n){ // fact.resize(n,1); // rep(i,n-1)fact[i+1]=fact[i]*(i+1); // } // using mint = ld; using mint = modint998244353;//static_modint<998244353> // using mint = modint1000000007;//static_modint<1000000007> // using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly // using mint = static_modint<469762049>; // ntt-friendly // using mint = static_modint<167772161>; // ntt-friendly // using mint = modint;//mint::set_mod(mod); // ll const mod=1000000007ll; // ll const mod=998244353ll; // ll modrui(ll a,ll b,ll mod){ // a%=mod; // if(b==0)return 1; // if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod; // return modrui(a*a%mod,b/2,mod)%mod; // } // void incr(vl &v,ll n){// n進法 // ll k=v.size(); // v[k-1]++; // ll now=k-1; // while (v[now]>=n) // { // v[now]=0; // if(now==0)break; // v[now-1]++; // now--; // } // return; // } // vector fact,invf; // void init_modfact(ll sz){ // fact.resize(sz); // invf.resize(sz); // fact[0]=1; // rep(i,sz-1){ // fact[i+1]=fact[i]*(i+1); // } // invf[sz-1]=1/fact[sz-1]; // for(ll i=sz-2; i>=0; i--){ // invf[i]=invf[i+1]*(i+1); // } // } // mint choose(ll n,ll r){ // if(n modpow,invpow; // void init_modpow(ll x,ll sz){ // mint inv=1/mint(x); // modpow.assign(sz,1); // invpow.assign(sz,1); // rep(i,sz-1){ // modpow[i+1]=modpow[i]*x; // invpow[i+1]=invpow[i]*inv; // } // } // long long phi(long long n) {// O(sqrt(n)) // long long res = n; // for (long long i = 2; i * i <= n; i++) { // if (n % i == 0) { // res -= res / i; // while (n % i == 0) n /= i; // } // } // if (n > 1) res -= res / n; // return res; // } // https://atcoder.jp/contests/abc314/submissions/73171689 // シンプルなテンプレート AVL 木(multiset 互換の最小実装) // - T: キーの型 // - Comp: 比較関数(デフォルト less)これで中身は昇順に並ぶ // 提供する主なメソッド: // insert(const T& key) -> int (挿入位置の index) // erase(const T& key) -> int (削除した index、存在しなければ -1) // erase_all(const T& key) -> int (削除した個数) // contains(const T& key) -> bool // lower_bound(const T& key) -> Iterator (最小の >= key の index) // upper_bound(const T& key) -> Iterator (最小の > key の index) // at(int k) -> optional (0-indexed k-th 要素) // rank(const T& key) -> number of elements < key // size(), empty(), to_vector() template > struct AVLtree { struct Node { T key; Node *l = nullptr, *r = nullptr, *p = nullptr; int height = 1; int sz = 1; Node(const T& k): key(k) {} }; Node* root = nullptr; Comp comp; AVLtree() = default; ~AVLtree(){ clear(); } void clear(){ destroy(root); root = nullptr; } int size() const { return root ? root->sz : 0; } bool empty() const { return root == nullptr; } // --- utilities --- static int height(Node* x){ return x ? x->height : 0; } static int sz(Node* x){ return x ? x->sz : 0; } static void update(Node* x){ if(!x) return; x->height = 1 + max(height(x->l), height(x->r)); x->sz = 1 + sz(x->l) + sz(x->r); if(x->l) x->l->p = x; if(x->r) x->r->p = x; } static int bf(Node* x){ return x ? height(x->l) - height(x->r) : 0; } Node* rotate_right(Node* y){ Node* x = y->l; Node* b = x->r; x->r = y; y->l = b; if(b) b->p = y; x->p = y->p; y->p = x; update(y); update(x); return x; } Node* rotate_left(Node* x){ Node* y = x->r; Node* b = y->l; y->l = x; x->r = b; if(b) b->p = x; y->p = x->p; x->p = y; update(x); update(y); return y; } // rebalance subtree rooted at x, returns new root of this subtree Node* rebalance(Node* x){ update(x); int balance = bf(x); if(balance > 1){ if(bf(x->l) < 0) x->l = rotate_left(x->l); return rotate_right(x); }else if(balance < -1){ if(bf(x->r) > 0) x->r = rotate_right(x->r); return rotate_left(x); } return x; } // recursive insert helper, duplicates allowed (insert into right subtree) pair insert_node(Node* node, const T& key){ if(!node) return { new Node(key), true }; if(comp(key, node->key)){ auto pr = insert_node(node->l, key); node->l = pr.first; if(node->l) node->l->p = node; }else{ // duplicates also go to right subtree -> multiset 挙動 auto pr = insert_node(node->r, key); node->r = pr.first; if(node->r) node->r->p = node; } node = rebalance(node); return { node, true }; } // insert: always inserts (returns index) int insert(const T& key){ int idx = rank(key); auto pr = insert_node(root, key); root = pr.first; if(root) root->p = nullptr; return idx; } // find min in subtree static Node* find_min(Node* x){ while(x && x->l) x = x->l; return x; } static Node* find_max(Node* x){ while(x && x->r) x = x->r; return x; } // erase by index (0-indexed), returns new subtree root and whether erased pair erase_kth(Node* node, int k){ if(!node) return { nullptr, false }; int lsz = sz(node->l); if(k < lsz){ auto pr = erase_kth(node->l, k); node->l = pr.first; if(node->l) node->l->p = node; node = rebalance(node); return { node, pr.second }; } if(k > lsz){ auto pr = erase_kth(node->r, k - lsz - 1); node->r = pr.first; if(node->r) node->r->p = node; node = rebalance(node); return { node, pr.second }; } // k == lsz -> delete this node if(!node->l || !node->r){ Node* tmp = node->l ? node->l : node->r; if(tmp) tmp->p = node->p; delete node; return { tmp, true }; } // two children: replace with successor (min in right subtree) Node* succ = find_min(node->r); node->key = succ->key; auto pr = erase_kth(node->r, 0); node->r = pr.first; if(node->r) node->r->p = node; node = rebalance(node); return { node, true }; } // erase a single occurrence; return erased index, or -1 if not found int erase(const T& key){ int idx = lower_bound(key).index(); if(idx >= size()) return -1; auto o = at(idx); if(!o || comp(key, *o) || comp(*o, key)) return -1; auto pr = erase_kth(root, idx); root = pr.first; if(root) root->p = nullptr; return pr.second ? idx : -1; } // erase all occurrences of key, return number removed int erase_all(const T& key){ int cnt = 0; while(true){ int idx = erase(key); if(idx == -1) break; ++cnt; } return cnt; } bool contains(const T& key) const { Node* cur = root; while(cur){ if(comp(key, cur->key)) cur = cur->l; else if(comp(cur->key, key)) cur = cur->r; else return true; } return false; } // count occurrences of key int count(const T& key) const { // number of elements < key と < upper_bound の差で求める int lo = rank(key); optional ub = upper_bound(key); int hi = ub ? rank(*ub) : size(); return hi - lo; } // k-th (0-indexed). return optional optional at(int k) const { if(k < 0 || k >= size()) return nullopt; Node* cur = root; while(cur){ int lsz = sz(cur->l); if(k < lsz) cur = cur->l; else if(k == lsz) return cur->key; else { k -= lsz + 1; cur = cur->r; } } return nullopt; } // number of elements strictly less than key int rank(const T& key) const { int r = 0; Node* cur = root; while(cur){ if(comp(key, cur->key)){ cur = cur->l; }else{ if(!comp(cur->key, key)) { // cur->key >= key cur = cur->l; } else { r += 1 + sz(cur->l); cur = cur->r; } } } return r; } // --- iterator-like interface (index-based iterator) --- struct Iterator { const AVLtree* tree = nullptr; int idx = 0; // 0..size() Iterator() = default; Iterator(const AVLtree* t, int i): tree(t), idx(i) {} T operator*() const { auto o = tree->at(idx); return *o; // assume valid } Iterator& operator++(){ ++idx; return *this; } // prefix Iterator& operator--(){ --idx; return *this; } // prefix Iterator& operator+=(int k){ idx += k; return *this; } Iterator& operator-=(int k){ idx -= k; return *this; } Iterator operator+(int k) const { return Iterator(tree, idx + k); } Iterator operator-(int k) const { return Iterator(tree, idx - k); } int index() const { return idx; } bool valid() const { return tree && idx >= 0 && idx < tree->size(); } }; // lower_bound: returns iterator to first element >= key (index) Iterator lower_bound(const T& key) const { int idx = 0; Node* cur = root; int ans = size(); while(cur){ if(!comp(cur->key, key)){ // cur->key >= key ans = idx + sz(cur->l); cur = cur->l; }else{ idx += 1 + sz(cur->l); cur = cur->r; } } return Iterator(this, ans); } // upper_bound: returns iterator to first element > key (index) Iterator upper_bound(const T& key) const { int idx = 0; Node* cur = root; int ans = size(); while(cur){ if(comp(key, cur->key)){ // key < cur->key ans = idx + sz(cur->l); cur = cur->l; } else { idx += 1 + sz(cur->l); cur = cur->r; } } return Iterator(this, ans); } // inorder to vector void inorder(Node* t, vector& out) const { if(!t) return; inorder(t->l, out); out.push_back(t->key); inorder(t->r, out); } vector to_vector() const { vector v; v.reserve(size()); inorder(root, v); return v; } private: void destroy(Node* t){ if(!t) return; destroy(t->l); destroy(t->r); delete t; } }; void solve() { ll n; cin >> n; vl v(n,0); rep(i,n-1){ cout << "? " << 1 << " " << i+2 << endl; cin >> v[i+1]; } for(ll i=n-1;i>0;i--){ v[i]-=v[i-1]; } AVLtree st; rep(i,n)st.insert(i); vl ans(n,-1); rep(i,n){ ans[n-1-i]=*st.at(st.size()-1-v[n-1-i]); st.erase(*st.at(st.size()-1-v[n-1-i])); } cout << "! "; rep(i,n)cout << ans[i]+1 << " \n"[i==n-1]; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); // ll mx=450; // vc fl(mx+1,0); // for(ll d=2;d<=mx;d++){ // if(fl[d])continue; // ll x=d; // ps.push_back(x); // while(x<=mx){ // fl[x]=1; // x+=d; // } // } ll t = 1; // cin >> t; while (t--){ solve(); } }