AT_aalc001_u 2 番目

For a sequence $ B=(B_1,B_2,\ldots,B_M) $ of length $ M $ , let $ C=(C_1,C_2,\ldots,C_M) $ be the sequence obtained by sorting it in ascending order. When $ M\geq 4 $ , define the **score** of $ B $ as $ C_{M-1}-C_2 $ . You are given a sequence of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ ( $ 4\leq N $ ). Partition $ A $ into $ 1 $ or more contiguous subsequences, each of length at least $ 4 $ . Find the maximum possible sum of the scores of all contiguous subsequences obtained by the partition. Each input file contains $ T $ test cases. Solve all of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print $ T $ lines. The $ i $ -th line should contain the answer to the $ i $ -th test case.

### Sample Explanation 1 For test case $ 1 $ , take the entire sequence as $ 1 $ contiguous subsequence. Sorting it in ascending order gives $ (1,2,10,20) $ , so its score is $ 10-2=8 $ . This is the maximum. For test case $ 2 $ , partitioning $ A $ into $ (0,0,1,1) $ and $ (0,0,1,1) $ gives a total score of $ 2 $ . This is the maximum. ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 4 \leq N \leq 4 \times 10^5 $ - $ 0 \leq A_i \leq 10^9 $ - The sum of $ N $ over all test cases in a single input file is at most $ 4 \times 10^5 $ . - All numerical values in the input are integers.