この問題はインタラクティブ問題です。

跳蚤デザート店のカウンターには、色とりどりの二層のゼリーが二列に並べられています（上の層を $a$、下の層を $b$ とします）。店の「凝固相補」という規則により、各組のゼリーの上の層と下の層の高さの和は、ちょうど $n+1$ です。もともと店員はこの二列のゼリーを高さに従って $1 \sim n$ の完全な順列になるように並べていましたが、昨夜、活発な跳蚤の店員がうっかりいくつかの位置で上下のゼリーを逆にしてしまいました！

今、年に一度のデザート祭りがまもなく開幕します。店員たちは、ゼリーが逆にされる前の初期の配置（すなわち、逆にされる前の上の層のゼリーの高さの列 $a$）を復元しなければなりません。

ゼリーの高さを直接見ることはできませんが、デザート店の自動測定器に指示を出すことはできます。いくつかの位置 $i$ を指定すると、測定器はその位置の上下のゼリーを入れ替え、現在の上の層のゼリーの最大の高さと最小の高さの差（範囲）と、下の層のゼリーの最大の高さと最小の高さの差（範囲）を返します。注意：各入れ替え操作の効果はその後も保持されます。

限られた回数の入れ替えと測定で、最初の上の層のゼリーの配置の列を復元できるでしょうか？

インタラクションライブラリは、まず $1\sim n$ の順列 $p$ を選び、順列 $b_i=n+1-p_i$ を構成します。その後、各添字 $i$ について、位置 $i$ にある二つの数を交換するかどうかを独立に決めます。交換を終えた後の配列を $a,b$ とします。この時点でも常に $a_i+b_i=n+1$ ですが、$a,b$ は必ずしも順列ではありません。

あなたは $n$ を知っていますが、この二つの配列は知りません。いくつかの位置を選び、その位置の $a_i,b_i$ を交換できます。インタラクションライブラリは、交換後の二つの配列の範囲を知らせます。各交換の効果はその後も保持されます。

あなたの課題は、最初のクエリを行う前の配列 $a$ を復元することです。返した配列の各値 $x$ をすべて同時に $n+1-x$ に置き換えて初めて目的の配列と一致する場合も、正解とみなされます。

実装の詳細

main 関数を実装する必要はなく、実装してはいけません。

ソースファイル recover.cpp でヘッダーファイル range.h をインクルードし、次の関数を実装してください。

std::vector<int> recover(int c, int n);

• $c$ は現在の小課題の番号で、本番のテストでは $1,2,3,4$、入出力例では $0$ です。$n$ は配列の長さです。インタラクションライブラリは各テストケースについて recover をちょうど一度呼び出します。
• 戻り値は長さ $n$ の整数配列でなければならず、最初のクエリを行う前の $a$、またはその各値をすべて相補の値に置き換えた配列を表します。

次の関数を呼び出すことができます。

std::pair<int, int> query(const std::vector<int>& positions);

• positions 内の添字は互いに異なり、$[0,n-1]$ に属していなければなりません。空の配列を渡すこともできます。
• インタラクションライブラリは、positions 内の各添字について現在の $a_i,b_i$ を一度ずつ交換し、その後、現在の $a$ の範囲と現在の $b$ の範囲を返します。クエリ間で交換の効果は累積しますが、解答として返すべきものは交換前の初期の配列を復元したものです。
• 範囲は、配列の最大値から最小値を引いた値と定義されます。常に $b_i=n+1-a_i$ なので、二つの範囲は必ず等しくなります。
• query の呼び出し回数は、そのテストケースの上限 $Q_{\max}$ を超えてはいけません。

インタラクションライブラリは適応的ではありません。初期の配列は recover が始まる前に決定されており、あなたのクエリに応じて初期の配列が変わることはありません。最終的な採点に使われるインタラクションライブラリは、配布されたサンプルのライブラリと異なる場合があります。提出プログラムは、ライブラリ内部のデータを読み取ったり、標準入力や標準出力のストリームを直接操作したりしてはいけません。

プログラムのテスト方法

recover.cpp、range.h、および添付ファイルの grader.cpp を同じディレクトリに置き、C++17 でコンパイルしてください。

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

ローカルのインタラクションライブラリが読み込む入力の1行目は $c,n,Q_{\max}$、2行目は順列 $p_0,\ldots,p_{n-1}$、3行目は $n$ 個の $0/1$ の数です。$1$ は、インタラクションの開始前にその位置を交換することを表します。関数の引数として渡されるのは $c,n$ だけで、順列、交換を表すフラグ、およびクエリ回数の上限は提出プログラムに直接渡されません。

解答が正しければ、ローカルのインタラクションライブラリは1行目に Correct!、2行目に Queries used: Q を出力します。ここで $Q$ は今回の呼び出しで使ったクエリの回数です。解答が誤っている場合は Wrong answer. を出力します。インターフェースの呼び出しが不正な場合は、標準エラー出力にもエラーの原因を出力します。

入出力例

入力 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

出力 1

Correct!
Queries used: 16

注記

この例では、インタラクション開始前の配列は $a=(3,6,1,4,5,5)$ で、その各値をすべて相補の値に置き換えた配列は $(4,1,6,3,2,2)$ です。どちらを返しても正解となります。最初の query({}) の呼び出しは $(5,5)$ を返します。上記の出力は、添付された模範プログラムの実行結果に対応しています。異なる正しいプログラムでは、クエリの回数が異なる場合があります。

制約

すべてのテストデータについて、$1\le n\le 500$ です。

各小課題の得点は、その小課題の中で得点倍率が最も低いテストケースに基づいて決まります。詳細は以下の通りです。

小課題

recover が返した解答が正しくない場合、query の引数が不正な場合、またはクエリ回数が $Q_{\max}$ を超えた場合、そのテストケースの得点は $0$ です。

それ以外の場合、小課題 $1,2$ では、そのテストケースについて満点を得ます。小課題 $3,4$ では、そのテストケースで実際に使ったクエリの回数を $Q$ とし、得点倍率 $f(Q)$ を次の表に従って計算します。

小課題 $3$ の得点は $40f(Q)$、小課題 $4$ の得点は $40f(Q)$ です。最終的な得点は、小数点以下 $3$ 桁に四捨五入されます。

実行時間制限：$2\ \mathrm{s}$。

メモリ制限：$512\ \mathrm{MiB}$。