Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Paranoid Trading

By mainstring · Limits 5s, 512 MB

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.

Input

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.

Output

For each test case, print a single number denoting the maximum profit made.

Sample

InputOutput
2
11
0 1 2 3 2 1 2 1 2 3 4
5
5 4 3 2 1
6
0

Discussion

Statistics


19% Solution Ratio

Takik_Earliest, Sep '19

SwampFireFastest, 1.4s

longlongintLightest, 3.9 MB

TasdidShortest, 450B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.