AT_aalc001_u 2 番目

長さ $ M $ の数列 $ B=(B_1,B_2,\ldots,B_M) $ を昇順に並べ替えて得られる数列を $ C=(C_1,C_2,\ldots,C_M) $ とします。 $ M\geq 4 $ であるとき、 $ B $ の**スコア**を $ C_{M-1}-C_2 $ と定めます。 長さ $ N $ ( $ 4\leq N $ )の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ A $ を、それぞれの長さが $ 4 $ 以上である $ 1 $ 個以上の連続部分列に分割します。 このとき、分割して得られたすべての連続部分列のスコアの総和としてあり得る最大値を求めてください。 $ 1 $ つの入力ファイルにつき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、数列全体を $ 1 $ 個の連続部分列とします。 これを昇順に並べ替えると $ (1,2,10,20) $ となるため、スコアは $ 10-2=8 $ です。これが最大値です。 $ 2 $ 番目のテストケースでは、 $ A $ を $ (0,0,1,1) $ と $ (0,0,1,1) $ に分割すると、 スコアの総和は $ 2 $ となります。これが最大値です。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 4 \leq N \leq 4 \times 10^5 $ - $ 0 \leq A_i \leq 10^9 $ - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 4 \times 10^5 $ 以下 - 入力される数値はすべて整数