H - Operator of Sense
問題文
整数 $X$ が与えられます。正の整数 $a,b$ に対して、 $f(a,b)$ を以下の手順で計算される値とします。
- $a=b$ のとき、 $f(a,b)=X$ である。
- それ以外の場合、 $f(a,b)$ は $a$ , $b$ のうち大きいほうの値に等しい。
正の整数からなる長さ $N$ の整数列 $(A _ 1,A _ 2,\ldots , A _ N)$ が与えられます。次の操作を $N-1$ 回繰り返します。
- 隣接する $2$ 要素を選び、その値を $a,b$ とします。選んだ $2$ 要素を取り除き、その場所に $f(a,b)$ を $1$ つ挿入します。
数列の長さは $1$ になるので、その要素の値としてあり得る最大値を求めてください。
$1$ 回の実行で $T$ 個 ($1\leq T$) のテストケースについて解いてください。
制約
- $1 \leq T \leq 10{,}000$
- $1 \leq N \leq 200{,}000$
- $0 \leq X \leq 10^{9}$
- $0 \leq A _ i \leq 10^{9}$
- $1$ 回の実行で与えられるテストケース全体で、 $N$ の総和は $200{,}000$ 以下である
- 入力はすべて整数
入力
$1$ 行目にテストケースの個数 $T$ が入力されます。
$2$ 行目以降、 $T$ 個のテストケースが順に入力されます。各テストケースは以下の形式で与えられます。
$N$ $X$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
出力
各テストケースに対する答えとなる整数を、順に、改行区切りで出力してください。
4
3 0
3 3 3
3 0
4 4 6
3 9
4 4 6
4 0
100 100 100 100
3
6
9
0
$1$ つめのテストケースでは、操作によって以下のように数列が変化します。最終的な要素の最大値は $3$ です。
-
最初に先頭から $1$ 番目と $2$ 番目の要素を選んだ場合、 $f(3,3)=X=0$ であるため、数列は $(0,3)$ になります。次に、先頭から $1$ 番目と $2$ 番目の要素を選びます。 $f(0,3)=3$ であるため、数列は $(3)$ になります。
-
最初に先頭から $2$ 番目と $3$ 番目の要素を選んだ場合、 $f(3,3)=X=0$ 、 $f(3,0)=3$ であるため、最終的な数列は $(3)$ になります。
$2$ つめのテストケースでは、最終的な要素の値は以下のように決まります。最終的な要素の最大値は $6$ です。
-
最初に先頭から $1$ 番目と $2$ 番目の要素を選んだ場合、 $f(4,4)=X=0$ 、 $f(0,6)=6$ であるため、最終的な数列は $(6)$ になります。
-
最初に先頭から $2$ 番目と $3$ 番目の要素を選んだ場合、 $f(4,6)=6$ 、 $f(4,6)=6$ であるため、最終的な数列は $(6)$ になります。
$3$ つめのテストケースでは、最終的な要素の値は以下のように決まります。最終的な要素の最大値は $9$ です。
-
最初に先頭から $1$ 番目と $2$ 番目の要素を選んだ場合、 $f(4,4)=X=9$ 、 $f(9,6)=9$ であるため、最終的な数列は $(9)$ になります。
-
最初に先頭から $2$ 番目と $3$ 番目の要素を選んだ場合、 $f(4,6)=6$ 、 $f(4,6)=6$ であるため、最終的な数列は $(6)$ になります。