You have been newly appointed as the accountant of Michael Corleone - the famous mafia boss. Your task is to trade for him in the stock market. This stock market of this town is fairly strange. You can buy at most one stock every day. And the difference of stock values between two consecutive days is either +1 or -1.
Working for a mafia family is not an easy job; you know that. So you have to strictly follow the following rules set by Michael himself:
You cannot buy and sell on the same day.
You can only buy a stock if you have no unsold stocks left.
You cannot deteriorate in any trade from the previous one. That means if you are selling a stock, your profit on this sale should be greater or equal to the profit from last sale (only last one sale). However, for the first sale, you are allowed to make any amount of profit.
Given N days of stock values, you have to find the maximum profit you can achieve.
First line contains an integer T (1 ≤ T ≤ 100) the number of test cases.
For each case, you’ll be given N (2 ≤ N ≤ 1000), the number of days. The following line contains N integers. The i-th integer, Si (0 ≤ Si ≤ 1000) denotes the value of the stock on the i-th day.
For each test case, print a single number denoting the maximum profit made.
| Input | Output |
|---|---|
2 11 0 1 2 3 2 1 2 1 2 3 4 5 5 4 3 2 1 | 6 0 |