[Solution] Mainak and Array Codeforces Solution

A. Mainak and Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mainak has an array 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,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≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$, and any positive integer 𝑘$k$.
• Repeat this 𝑘$k$ times: set 𝑎𝑙=𝑎𝑙+1,𝑎𝑙+1=𝑎𝑙+2,…,𝑎𝑟−1=𝑎𝑟,𝑎𝑟=𝑎𝑙$a_l=a_{l+1},a_{l+1}=a_{l+2},\dots ,a_{r-1}=a_r,a_r=a_l$ (all changes happen at the same time).

Mainak wants to maximize the value of (𝑎𝑛−𝑎1)$(a_n-a_1)$ after exactly one such operation. Determine the maximum value of (𝑎𝑛−𝑎1)$(a_n-a_1)$ that he can obtain.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤50$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≤𝑛≤2000$1\le n\le 2000$).

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤999$1\le a_i\le 999$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2000$2000$.

Output

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

Note

• In the first test case, we can rotate the subarray from index 3$3$ to index 6$6$ by an amount of 2$2$ (i.e. choose 𝑙=3$l=3$, 𝑟=6$r=6$ and 𝑘=2$k=2$) to get the optimal array:So the answer is 𝑎𝑛−𝑎1=11−1=10$a_n-a_1=11-1=10$.
• In the second testcase, it is optimal to rotate the subarray starting and ending at index 1$1$ and rotating it by an amount of 2$2$.
• In the fourth testcase, it is optimal to rotate the subarray starting from index 1$1$ to index 4$4$ and rotating it by an amount of 1$1$. So the answer is 8−1=7$8-1=7$.