CF2062C Cirno and Operations

Cirno has a sequence $ a $ of length $ n $ . She can perform either of the following two operations for any (possibly, zero) times unless the current length of $ a $ is $ 1 $ : - Reverse the sequence. Formally, $ [a_1,a_2,\ldots,a_n] $ becomes $ [a_n,a_{n-1},\ldots,a_1] $ after the operation. - Replace the sequence with its difference sequence. Formally, $ [a_1,a_2,\ldots,a_n] $ becomes $ [a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}] $ after the operation. Find the maximum possible sum of elements of $ a $ after all operations.

The first line of input contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of input test cases. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 50 $ ) — the length of sequence $ a $ . The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ |a_i|\le 1000 $ ) — the sequence $ a $ .

For each test case, print an integer representing the maximum possible sum.

In the first test case, Cirno can not perform any operation, so the answer is $ -1000 $ . In the second test case, Cirno firstly reverses the sequence, then replaces the sequence with its difference sequence: $ [5,-3]\to[-3,5]\to[8] $ . It can be proven that this maximizes the sum, so the answer is $ 8 $ . In the third test case, Cirno can choose not to operate, so the answer is $ 1001 $ .