Description

Recently, more and more people have been investing in the stock market, and Ah Fu is also a bit tempted. Keeping in mind that "the stock market is risky, and investment requires caution," Ah Fu decides to first study a simplified version of the stock trading problem.
Suppose Ah Fu has accurately predicted the price of a certain stock over the next N days. He wants to make two trades to maximize his profit. For simplicity, the profit is calculated as the selling price minus the buying price.
Multiple trades can be conducted on the same day. However, after the first purchase, it must be sold before the second purchase can be made.
Now, Ah Fu wants to know the maximum profit he can achieve.

Input Format

The first line of input is an integer T (T ≤ 50), indicating the number of test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100,000), representing the number of days.
The second line consists of N space-separated integers, representing the stock price for each day. The absolute value of the stock price on any given day will not exceed 1,000,000.

Output Format

For each test case, output one line.
The line contains an integer, representing the maximum profit Ah Fu can achieve.

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

28
2
0

Hint

For the first sample input, Afu can buy on the first day (price: 5) and sell on the second day (price: 14) for the first transaction. Then buy on the third day (price: -2) and sell on the seventh day (price: 17) for the second transaction. The total profit is (14-5)+(17-(-2))=28.
For the second sample input, Afu can buy on the first day (price: 6) and sell on the second day (price: 8) for the first transaction. Then buy again on the second day and sell on the same day for the second transaction. The total profit is 8-6=2.
For the third sample input, since the prices are continuously falling, Afu can choose any day to buy and immediately sell. The maximum profit achievable is 0.
Classic algorithm—search on Baidu to deeply understand.