Maximum Melody Score

You are given k melodies. Each melody is described by an integer n and a sequence of n integers representing the frequencies of the notes. For each melody, your task is to determine the maximum score, where the score of a contiguous subarray is defined as the difference between the maximum and minimum frequency in that subarray. In mathematical terms, for a subarray from index i to j (1-based indexing), the score is given by:

\(score = \max_{1 \leq i \leq j \leq n}\Big(\max_{i \leq k \leq j} a_k - \min_{i \leq k \leq j} a_k\Big)\)

Print the maximum score for each melody on a separate line.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer k representing the number of melodies.
• Then, for each melody, there are two lines:
  • The first line contains an integer n — the number of frequencies in the melody.
  • The second line contains n space-separated integers representing the frequencies.

outputFormat

For each melody, output a single integer, which is the maximum possible score computed as the difference between the maximum and minimum frequency among all contiguous subarrays. Each result should be printed on its own line.

## sample

1
1
1

0

</p>