CF1726A Mainak and Array

Mainak has an array $ a_1, a_2, \ldots, a_n $ of $ n $ positive integers. He will do the following operation to this array exactly once: - Pick a subsegment of this array and cyclically rotate it by any amount. Formally, he can do the following exactly once:- Pick two integers $ l $ and $ r $ , such that $ 1 \le l \le r \le n $ , and any positive integer $ k $ . - Repeat this $ k $ times: set $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $ (all changes happen at the same time). Mainak wants to maximize the value of $ (a_n - a_1) $ after exactly one such operation. Determine the maximum value of $ (a_n - a_1) $ that he can obtain.

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 50 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 999 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

For each test case, output a single integer — the maximum value of $ (a_n - a_1) $ that Mainak can obtain by doing the operation exactly once.

- In the first test case, we can rotate the subarray from index $ 3 $ to index $ 6 $ by an amount of $ 2 $ (i.e. choose $ l = 3 $ , $ r = 6 $ and $ k = 2 $ ) to get the optimal array: $ $$$[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}] $ $ So the answer is $ a\_n - a\_1 = 11 - 1 = 10 $ .

In the second testcase, it is optimal to rotate the subarray starting and ending at index $ 1 $ and rotating it by an amount of $ 2 $ .

In the fourth testcase, it is optimal to rotate the subarray starting from index $ 1 $ to index $ 4 $ and rotating it by an amount of $ 3 $ . So the answer is $ 8 - 1 = 7$$$.