Half Selection Game

問題文

正整数 $N$ と、長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ があります。

Alice と Bob はゲームを行います。ゲームは以下の手続きで進行します。

1. Alice は整数 $X$ を一つ選び、 Bob に知らせる。
2. Alice を先手として、 Alice と Bob は以下の操作を $A$ の長さが $1$ になるまで交互に行う。ここで $m$ を操作を行う直前の $A$ の長さとする。
   • 手番のプレイヤーが $(A_1, A_2, \cdots, A_{\lfloor m/2 \rfloor})$ か $(A_{\lfloor m/2 \rfloor + 1}, A_{\lfloor m/2 \rfloor + 2}, \cdots, A_m)$ のどちらか一方の数列を選ぶ。 $A$ をその選んだ数列に置き換える。
3. 最後に $A$ に残った唯一の要素を $Y$ とする。最終的な スコア を $|X - Y|$ と定める。

Alice の目標はスコアをできるだけ小さくすることであり、 Bob の目標はスコアをできるだけ大きくすることです。
両者とも最善を尽くしたときにおけるスコアの値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \le T \le 10^5$
• $2 \le N \le 3 \times 10^5$
• すべてのテストケースにおける $N$ の総和は $3 \times 10^5$ 以下
• $1 \le A_i \le 10^9 \enspace (1 \le i \le N)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

サンプル 1

入力

3
4
1 5 2 4
3
1000000000 10 1
7
63 5 96 63 22 8 97

出力

1
0
7

$1$ 番目のテストケースについて、例えば以下の手続きでゲームが進行します。

• Alice が $X = 3$ を選び、 Bob に知らせる。
• Alice が $(1, 5)$ と $(2, 4)$ のうち、後者を選ぶ。 $A = (2, 4)$ に更新される。
• Bob が $(2)$ と $(4)$ のうち、前者を選ぶ。 $A = (2)$ に更新される。
• $A$ の長さが $1$ になったので操作を終了する。 $A$ の唯一の要素 $Y$ は $2$ であるため、スコアは $|X - Y| = 1$ である。