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

皆さんは数ヶ月間 CZL の姿を見ていなかったことでしょう。彼が帰ってきました！私たちは小 U、小 Z、CZL の 3 人を 1 つの問題セットにまとめることに成功しました。

CZL はシャッフルされたカードの束を持っています。この束には上から順に $n$ 枚のカードがあり（カードの位置は $0$ から $n-1$ まで番号付けされています）、それぞれのカードには $0, 1, 2, \dots, n-1$ のいずれかの値が書かれています。異なるカードの値はすべて異なります。今、あなたはこの束の各カードの値を当てる必要があります。しかし、大魔術師である彼が簡単に教えてくれるはずがありません。

最初、CZL の左手と右手はどちらも $0$ 番目のカードの位置にあります。あなたは毎回、彼の左手を 1 枚上に移動させるか、下に移動させるかを指定できます。同様に、右手についても上に移動させるか、下に移動させるかを指定できます。また、左手のカードが右手のカードよりも小さいかどうかを尋ねることもできます。これらの操作を通じて、この束の各カードの値を上から順に特定してください。

CZL の手は非常に器用ですが、彼は他の人にもマジックを披露しなければなりません。そのため、合計 $7.0 \cdot 10^8$ 回以内の移動で、この束の各カードの値を特定してください。

あなたのコードにはヘッダーファイル "lancllords.h" を含める必要があり、以下の関数を実装する必要があります。

vector<int> answer(int n);

この関数の引数 $n$ はカードの枚数を表します。この関数は長さ $n$ の配列 $P$ を返す必要があり、P[i] は上から $i$ 番目のカードの値を表します。

CZL の左手が $p$ 番目のカードの位置に、右手が $q$ 番目のカードの位置にあると仮定します。あなたは以下の関数を呼び出すことができます。

void inc_p();

CZL の左手を 1 枚下の位置に移動させます。

void dec_p();

CZL の左手を 1 枚上の位置に移動させます。

void inc_q();

CZL の右手を 1 枚下の位置に移動させます。

void dec_q();

CZL の右手を 1 枚上の位置に移動させます。

bool cmp();

$p$ 番目のカードの値と $q$ 番目のカードの値を比較します。$p$ 番目のカードが $q$ 番目のカードより小さい場合は true を、そうでない場合は false を返します。

最初の 4 つの関数を呼び出すたびに、grader の変数 $cnt$ が 1 増加します。最終的な評価において、$cnt$ の値が大きすぎる場合、そのテストケースは不合格となります。常に $0 \le p, q < n$ を満たすようにしてください。満たさない場合も不合格となります。

最初の 4 つの関数の呼び出し回数が $7.0 \cdot 10^8$ 回以下、5 番目の関数の呼び出し回数が $10^7$ 回以下であれば、実行時間は 5 秒以内となります。つまり、あなたのコードには少なくとも 5 秒の実行時間が与えられます。

grader.cpp と lancllords_sample.cpp という 2 つのファイルを提供しています。lancllords_sample.cpp は解答のサンプルです。g++ lancllords.cpp grader.cpp -o lancllords -O2 というコマンドでプログラムをテストできます。

入力

1 行目にカードの枚数を表す正整数 $n$ が与えられます。

続く 1 行に $n$ 個の整数 $P_0, \dots, P_{n-1}$ が与えられ、上から $i$ 番目のカードの値を表します。

出力

インタラクティブライブラリによって情報が出力されます。ローカルテストにおいて、$p, q$ の値が範囲外になった場合は "Out of bound!" と出力されます。返した答えが間違っている場合は "Wrong answer!" と出力され、正解の場合は "Right Output!" と、最初の 4 つの関数を呼び出した回数が表示されます。

提供されたインタラクティブライブラリは最終的なものとは異なりますが、最終的なテストにおいても、カードの並び順は事前に生成されており、あなたの質問によって変化することはありません。

入出力例

入力 1

5
3 4 0 1 2

出力 1

Right Output!
You use 100 operations!

注記 1

このサンプルは、最初の 4 つの関数を 100 回呼び出し、最終的に正しい並び順を得たことを示しています。

入力 2

配布ファイルを参照してください。

出力 2

配布ファイルを参照してください。

入力 3

配布ファイルを参照してください。

出力 3

配布ファイルを参照してください。

小課題

すべてのデータについて $1 \le n \le 150000$ を満たします。

Subtask 1 (6 点): $n \le 1000$

Subtask 2 (7 点): $n \le 10000$

Subtask 3 (38 点): $n \le 30000$

Subtask 4 (25 点): $n \le 50000$

Subtask 5 (24 点): $n \le 150000$