use itertools::Itertools; use proconio::input; use crate::urectanc::binary_indexed_tree::BinaryIndexedTree; fn main() { input! { n: usize } let ask = |l: usize, r: usize| { println!("? {} {}", l + 1, r); input! { x: i64 } assert_ne!(x, -1); x as usize }; let mut bit = BinaryIndexedTree::from(vec![1; n]); let mut inv = ask(0, n); let mut p = vec![]; for i in 1..n { let ninv = ask(i, n); let idx = inv - ninv; let x = bit.max_right(|sum| (sum as usize) <= idx); bit.add(x, -1); p.push(x); inv = ninv; } let x = bit.max_right(|sum| sum <= 0); p.push(x); let ans = p.iter().map(|&p| p + 1).join(" "); println!("! {ans}"); } pub mod urectanc { pub mod binary_indexed_tree { use crate::urectanc::{clamp_range, num_traits}; use clamp_range::ClampRange; use num_traits::PrimitiveInteger; use std::ops::RangeBounds; pub struct BinaryIndexedTree { len: usize, tree: Vec, } impl From for BinaryIndexedTree where T: PrimitiveInteger, A: AsRef<[T]>, { fn from(a: A) -> Self { let a = a.as_ref(); let len = a.len(); let mut tree = vec![T::zero(); len + 1]; tree[1..].copy_from_slice(a); for i in 1..len { let lsb = i & i.wrapping_neg(); if i + lsb <= len { let add = tree[i]; tree[i + lsb] += add; } } Self { len, tree } } } impl BinaryIndexedTree where T: PrimitiveInteger, { pub fn new(len: usize) -> Self { Self { len, tree: vec![T::zero(); len + 1], } } pub fn to_vec(&self) -> Vec { let mut a = self.tree.clone(); for i in (1..self.len).rev() { let lsb = i & i.wrapping_neg(); if i + lsb <= self.len { let sub = a[i]; a[i + lsb] -= sub; } } a[1..].to_owned() } pub fn get(&self, i: usize) -> T { self.sum(i..=i) } pub fn set(&mut self, i: usize, x: T) { self.add(i, x - self.get(i)); } pub fn add(&mut self, i: usize, x: T) { let mut i = i + 1; while i <= self.len { self.tree[i] += x; i += i & i.wrapping_neg(); } } pub fn sum(&self, range: impl RangeBounds) -> T { let (mut l, mut r) = range.clamp(0, self.len); let mut sum = T::zero(); while l < r { sum += self.tree[r]; r -= r & r.wrapping_neg(); } while r < l { sum -= self.tree[l]; l -= l & l.wrapping_neg(); } sum } pub fn max_right(&self, f: impl Fn(T) -> bool) -> usize { let mut r = 0; let mut sum = T::zero(); assert!(f(sum)); let mut width = self.len.next_power_of_two(); while width > 0 { if r + width <= self.len && f(sum + self.tree[r + width]) { sum += self.tree[r + width]; r += width; } width >>= 1; } r } } } pub mod clamp_range { use std::ops::{Bound, RangeBounds}; pub trait ClampRange: RangeBounds { fn clamp(&self, l: usize, r: usize) -> (usize, usize) { assert!(l <= r); let start = match self.start_bound() { Bound::Included(&l) => l, Bound::Excluded(&l) => l + 1, Bound::Unbounded => l, } .clamp(l, r); let end = match self.end_bound() { Bound::Included(&r) => r + 1, Bound::Excluded(&r) => r, Bound::Unbounded => r, } .clamp(l, r); (start.min(end), end) } } impl ClampRange for T where T: RangeBounds {} } pub mod num_traits { use std::{ fmt::Debug, ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Rem, RemAssign, Sub, SubAssign}, }; pub trait PrimitiveInteger: 'static + Copy + Ord + Debug + Add + Sub + Mul + Div + Rem + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign { fn midpoint(self, rhs: Self) -> Self; fn rem_euclid(self, rhs: Self) -> Self; fn zero() -> Self; fn one() -> Self; fn min_value() -> Self; fn max_value() -> Self; } macro_rules! impl_primitive_integer { ($($ty:ty),*) => { $(impl PrimitiveInteger for $ty { fn midpoint(self, rhs : Self) -> Self { self.midpoint(rhs) } fn rem_euclid(self, rhs : Self) -> Self { self .rem_euclid(rhs) } fn zero() -> Self { 0 } fn one() -> Self { 1 } fn min_value() -> Self { Self::MIN } fn max_value() -> Self { Self::MAX } })* }; } impl_primitive_integer!( i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize ); } }