Maximize Stock Profit

You are given a list of stock prices for a series of days. Your task is to determine the maximum profit that can be made by buying on one day and selling on a later day. Formally, if the prices are given by p₁, p₂, ..., p_n, you need to compute the quantity

$$\max_{1 \le i < j \le n}(p_j - p_i)$$

If no profit can be achieved, output 0.

The program will be tested on multiple test cases. Read the input from stdin and write the result for each test case on a new line to stdout.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer N indicating the number of days.
• The second line contains N space-separated integers representing the stock prices on each day.

outputFormat

For each test case, output a single integer on a new line representing the maximum profit achievable. If no profit is possible, output 0.

2
6
7 1 5 3 6 4
5
7 6 4 3 1

5
0