## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${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\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},\dots ,{a}_{r-1}={a}_{r},{a}_{r}={a}_{l}$ (all changes happen at the same time).

Mainak wants to maximize the value of $\left({a}_{n}-{a}_{1}\right)$ after exactly one such operation. Determine the maximum value of $\left({a}_{n}-{a}_{1}\right)$ that he can obtain.

Input

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},\dots ,{a}_{n}$ ($1\le {a}_{i}\le 999$).

Solution Click Below:-  👉
👇👇👇👇👇

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

Output

For each test case, output a single integer — the maximum value of $\left({a}_{n}-{a}_{1}\right)$ that Mainak can obtain by doing the operation exactly once.

Note
• 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: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 $1$. So the answer is $8-1=7$.