Problem I: FIMO sequence

あなたの仕事は以下で定義される数列についてのシミュレーションをすることである。

初期状態でこの数列は空である。 数列の i 番目の要素は a_i で表記される。 また数列の最初の要素は a₁ である。 数列に対する操作は0から9の整数で与えられる。 以下でそれぞれについて説明する。

0: このクエリーは数 x と一緒に与えられる。 このクエリーが与えられたら数列に数 x を挿入する。 数列が空の時に挿入を行うと a₁ = x となる。 数列が n 個の要素を持っている時に挿入を行うと a_n+1 = x となる。 なおクエリーとして与えられる x は重複しないとする。

1: このクエリーが与えられたら数列内の数を1つ消去する。 数列の真ん中の数が消去される。 消去する数は,数列が n 個の値を持っているとすると数列の真ん中の数、 a_n/2 である。 n が奇数の場合は n/2 を切り上げしたものを利用してその数 a_⌈n/2⌉ を消去する。 数列が空の場合にこのクエリーがくることはない。 例えば現在数列が a₁ = 1 , a₂ = 2 , a₃ =3, a₄ =4, a₅ =5 だったとする。 この場合 a₃ が消去される。 その結果 a₁ =1, a₂ =2, a₃ =4, a₄ =5となる。 もう一つの例を示す。 数列が a₁ =1, a₂ =2, a₃ =3, a₄ =4 だったとする。 この状態で消去を行うと消去されるのは a₂ =2で消去した後数列は a₁ =1, a₂ =3, a₃ =4 となる。

2: 数列の前半部分とは、インデックスが1から⌈n/2⌉までの数である。 このクエリーが与えられたら数列の前半部分に含まれる数の中から最小値が何か求める。 数列の前半部分が空の場合にこのクエリーがくることはない。

以下に例を示す。
数列が{6,2,3,4,5,1,8}だとする。 この場合のこのクエリーに対する答えは前半部分{6,2,3,4}の中の最小値なので2になる。

3: このクエリーが与えられたら数列の後半部分、つまり前半部分に属さない数の中から最小値が何かを求める。 数列の後半部分が空の場合にこのクエリーがくることはない。

以下に例を示す。
数列が{6,2,3,4,5,1,8}だとする。 この場合このクエリーに対する答えは5,1,8の中の最小値1になる。

4: このクエリーは数 i と一緒に与えられる。 現在の数列の状態から挿入を行わずに消去を続けたと仮定する。 現在前半部分に含まれる数の中からクエリー2の結果になる可能性があるものがいくつかある。 その中で i 番目に小さい数を求める。 数列の前半部分が空のときにこのクエリーがくることはない。また i 番目の要素は必ず存在すると仮定してよい。

以下に例を示す。

数列{6,2,3,4,5,1,8}に対して値の消去を繰り返すとする。
{6,2,3,4,5,1,8}　前半部分の最小値は2
{6,2,3,5,1,8}    前半部分の最小値は2
{6,2,5,1,8}      前半部分の最小値は2
{6,2,1,8}        前半部分の最小値は2
{6,1,8}          前半部分の最小値は1
{6,8}            前半部分の最小値は6
{8}              前半部分の最小値は8
{}               前半部分は空である。

最初の状態で前半部分に含まれる数は{6,2,3,4}であり、 その中で前半部分の最小値になった数は2,6である。 この例では1番目に小さい数は2,2番目に小さい数は6である。

5: このクエリーは数 i と一緒に与えられる。 現在の数列の状態から挿入を行わずに消去を続けたと仮定する。 現在後半部分に含まれる数字の中からクエリー3の結果になる可能性があるものがいくつかある。 その中で i 番目に小さい物を求める。 数列の後半部分が空のときにこのクエリーがくることはない。また i 番目の要素は必ず存在すると仮定してよい。

以下に例を示す。

数列{6,2,3,4,5,1,8}に対して値の消去を繰り返すとする
{6,2,3,4,5,1,8} 　後半部分の最小値は1
{6,2,3,5,1,8}    後半部分の最小値は1
{6,2,5,1,8}      後半部分の最小値は1
{6,2,1,8}        後半部分の最小値は1
{6,1,8}          後半部分の最小値は8
{6,8}            後半部分の最小値は8
{8}              後半部分は空
{}               後半部分は空

最初の状態で後半部に含まれる数は{5,1,8}で その中で最小値になった1,8である。 この例では1番目に小さい数は1,2番目に小さい数は8である。

6: このクエリーが与えられたら数列の前半部分に含まれる数の中から最大の値が何か求める。 数列の前半部分が空の時、このクエリーは与えられない。

以下に例を示す。
数列が{1,3,2,5,9,6,7}だとする。 この場合このクエリーに対する答えは{1,3,2,5}の中の最大値なので5になる。

7: このクエリーが与えられたら数列の後半部分に含まれる数の中から最大の値が何かを求める。 数列の前半部分が空の時、このクエリーは与えられない。

以下に例を示す。
数列が{1,3,2,5,9,6,7}だとする。 この場合このクエリーに対する答えは{9,6,7}の中の最大値9になる。

8: このクエリーは数 i と一緒に与えられる。 現在の数列の状態から挿入を行わずに消去を続けたと仮定する。 現在前半部分に含まれる数の中からクエリー6の結果になる可能性があるものがいくつかある。 その中で i 番目に大きい数を求める。 数列の前半部分が空のときにこのクエリーがくることはない。また i 番目の要素は必ず存在すると仮定してよい。

以下に例を示す。

数列{1,3,2,5,9,6,7}に対して値の消去を繰り返すとする。
{1,3,2,5,9,6,7}　前半部分の最大値は5
{1,3,2,9,6,7}　  前半部分の最大値は3
{1,3,9,6,7}　    前半部分の最大値は9
{1,3,6,7}　      前半部分の最大値は3
{1,6,7}　        前半部分の最大値は6
{1,7}　          前半部分の最大値は1
{7}　            前半部分の最大値は7
{}　　　　　　　       前半部分は空

最初の状態で前半部分に含まれる数は{1,3,2,5}で、 その中で前半部分の最大値になった値は1,3,5である。 この例では1番目に大きい値は5,2番目に大きい値は3,3番目に大きい値は1である。

9: このクエリーは数字 i と一緒に与えられる。 現在の数列の状態から挿入を行わずに消去を続けたと仮定する。 現在後半部分に含まれる数の中からクエリー7の結果になる可能性があるものがいくつかある。 その中で i 番目に大きい数を求める。 数列の後半部分が空のときにこのクエリーがくることはない。また i 番目の要素は必ず存在すると仮定してよい。

以下に例を示す。

数列{1,3,2,5,9,6,7}に対して値の消去を繰り返すとする。
{1,3,2,5,9,6,7}　後半部分の最大値は9
{1,3,2,9,6,7}　  後半部分の最大値は9
{1,3,9,6,7}　    後半部分の最大値は7
{1,3,6,7}　      後半部分の最大値は7
{1,6,7}　        後半部分の最大値は7
{1,7}　          後半部分の最大値は7
{7}　            後半部分は空
{}              後半部分は空

最初の状態で後半部に含まれる数は9,6,7で、 その中で後半部分の最大値になった値は9,7である。 この例では1番目に大きい値は9,2番目に大きい値は7である。

Input

入力は複数のテストケースからなる。 最初の行にクエリの数が与えられる。

q
query0
・
・
・
qureyn-1

入力データにおけるクエリーの数の和は200000を超えない。 クエリ0,4,5,8,9はクエリ番号と数字のペアで与えられる。 クエリ1,2,3,6,7は一つの数字で与えられる。 なおクエリーが与えられた結果数列の長さが20000より大きくなることはないと仮定してよい。

Output

クエリが0だった場合は何も出力してはいけない。 クエリが1だった場合は消去された値を1行に出力せよ。 その他のクエリーについては求めた値を1行に出力せよ それぞれのケースについてすべてのクエリーを処理した時に"end"という1行(""は含まない)を出力すること。

Sample input

5
0 1
0 2
0 3
0 4
1
6
0 1
0 2
0 3
0 4
0 5
1
31
0 6
0 2
0 3
0 4
0 5
0 1
0 8
4 1
4 2
5 1
5 2
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
1
32
0 1
0 3
0 2
0 5
0 9
0 6
0 7
8 1
8 2
8 3
9 1
9 2
6
7
1
6
7
1
6
7
1
6
7
1
6
7
1
6
7
1
6
1
0

Sample output

2
end
3
end
2
6
1
8
2
1
4
2
1
3
2
1
5
2
1
2
1
8
1
6
8
6
8
8
end
5
3
1
9
7
5
9
5
3
9
2
9
7
9
3
7
3
6
7
6
1
7
1
7
7
end

---