D: Complex Oracle - Complex Oracle -

問題

※この問題はリアクティブ問題です．すなわち，サーバー側に用意されたプログラムと対話的に応答することで正答を導くプログラムを作成する必要があります． また、サーバー側のプログラムも計算機資源を共有する関係上、サーバーだけで最大 3 sec程度の実行時間、最大 300 MB程度のメモリを使用する場合がありますので、TLE・MLEにお気をつけください。

あいずにゃんは若ヶ松高校のプログラミングコンテスト部、通称ぷろこん部に所属する2年生である。見目麗しい。あいずにゃんはその小さな体も無限に存在するチャームポイントの1つであるが、本人はコンプレックスを感じているようだ。そのせいか、一列に並んでいる人たちを見ると、それぞれの人の前方にその人より身長が高い人が何人並んでいるかを瞬時に数えられる能力を持っている。

プロコンの名門・律命館大学中等部卒のエリート競技プログラマであり、ぷろこん部の部長であるりっつちゃんは、あいずにゃんのこの能力を使えば、並んでいる人たちがそれぞれ何番目に背が高いのかを当てることができるのではないかと考えた。

今、りっつちゃんはN人が並んでいる列をあいずにゃんに見せている。りっつちゃんは、人がN人並んでいることは知っているが、その並び順がどうなっているかはわからない。りっつちゃんはあいずにゃんに “l番目の人からr番目の人までコンプレックス度” を教えてもらうことができる。ここで、l番目の人からr番目の人までのコンプレックス度とは、i (l \≤ i \≤ r) 番目の人それぞれに関して、l番目からi − 1番目までの間にいる自分 (i) より背が高い人の人数の総和である。(より厳密な定義は入出力形式を参照のこと)

(うらやましいことに) ぷろこん部の部員であるあなたは、(とても、とても心苦しいが) あいずにゃんをオラクルとして利用することで身長順を当てるプログラムを書くようりっつちゃんに命じられた。つらい。せめてあいずにゃんに負担をかけないよう、少ない質問回数で求められるよう頑張ろう。

入力出力形式

サーバーは背の順を表す長さNの数列pを保持している。これは入力として与えられない。pの各要素p_iは1以上N以下であり、それぞれ値は異なる。p_iが大きい値を持つ方が背が高いことを表す。

サーバーはまず、pの長さNを表す1つの整数からなる1行を入力として解答プログラムに与える。

次に解答プログラムが2つの整数 l, r (1 \≤ l \≤ r \≤ N) からなるクエリをサーバーに送る。クエリの出力形式は

? l r

である。これは例えばC/C++だと、

printf("? %d %d\n", l, r); fflush(stdout);

などと書けばよい。出力の度にフラッシュすることを推奨する。

すると、サーバー側は以下の値を表す1つの整数Cからなる1行を入力として解答プログラムに与える。

C = (\{ (i, j) | p_i > p_j {\rm for} l \≤ i<j \≤ r \}の要素数)

ただし、クエリとして正しくないl, r (l, rが1以上N以下の数ではない、またはl>rである) が与えられた場合、サーバーは−1ã‚’Cとして返す。

この応答を何度か繰り返し、解答プログラムがpを推定できたならば、pを以下の形式で出力する。

! p_1 ... p_N

推定した順列の出力は1度しかできず、この出力がpと異なる場合、誤答となる。200,000回以内のクエリで正しいpを出力できた場合、正答となる。

各クエリで改行を行うよう気をつけること。

入力制約

入力出力例



サーバーの出力  サーバーへの入力


4  


  ? 1 3 


 2  


  ? 2 4 


 1  


 ...  ... 


  ! 4 1 3 2