Stock Trading

Problem Background

Special for beginners, ^_^

Problem Description

More and more people are joining the stock market lately, and Afu is also tempted. Remembering "the stock market is risky, enter with caution", Afu decided to first study a simplified version of the stock trading problem.

Suppose Afu has accurately predicted the price of a certain stock for the next $N$ days, and he wants to buy and sell it twice to maximize his profit. For simplicity, profit is calculated as the selling price minus the buying price.

Multiple trades can be made on the same day. However, after the first purchase, he must sell before he can buy a second time.

Now Afu wants to know the maximum profit he can obtain.

Input Format

The first line of input is an integer $T\ (T\le 50)$, indicating there are $T$ test cases in total.

For each test case, the first line is an integer $N\ (1\le N\le 100\,000)$, the number of days. The second line contains $N$ space-separated integers, the price of the stock on each day. The absolute value of the stock price on each day does not exceed $1\,000\,000$.

Output Format

For each test case, output one line containing an integer: the maximum profit Afu can obtain.

Sample Input 1

3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2

Sample Output 1

28
2
0

Hint

For the first sample, Afu can buy on day $1$ (price $5$) and sell on day $2$ (price $14$) for the first trade. Then buy on day $3$ (price $-2$) and sell on day $7$ (price $17$) for the second trade. Total profit is $(14-5)+(17-(-2))=28$.

For the second sample, Afu can buy on day $1$ (price $6$) and sell on day $2$ (price $8$) for the first trade. Then buy and sell again on day $2$. Total profit is $8-6=2$.

For the third sample, since the price keeps falling, Afu can buy on any day and sell quickly. The maximum profit is $0$.

Constraints

Time limit 1s, memory limit 1024KiB for each test case.