"With great PPOs comes great powers". Digo recently got a PPO from MacroHard but
he always miss a great part of life, a good girlfriend. His pay is very good and with that
earned money, he can buy very large amount of powers from GOD (but not a girl of
course). One day he was visiting Jupiter with his friends. On Jupiter there are a large
number of mountains. One girl did not like the random heights of the mountains and so
she asked Digo to make heights of all the mountains such that they all become in non-
decreasing order of height. For this task Digo will have to buy powers from GOD. The
GOD has only one kind of power left in stock. The description of the power is:
- One packet of power will increase the height of all the mountains from a choosen
index up to the end by 1m.
- One packet of power costs $1.
Now Digo wants to spend minimum possible amount on this task. Please help him in his
quest to impress the girl.
Input:
First line contains 't' - no, of test cases.
Then next t lines follow, consisting of 'n' (no. of mountains) followed by n
numbers (Height of corresponding mountain).
Output:
't' lines with the answer to the each test case(Minimum amount of money to be
used to fulfill girlfriends desire).
Constraints:
T<=5
N<=1000000
0<=Mountain height<=1000000 (meters)
Sample:
Input:
2
5 1 2 2 3 3
5 2 1 2 1 3
Output:
0
2
Explanation:
In first case all the mountains are already in non-decreasing form. No power
required to be purchased.
In second case , Digo will increase the height of mountain 4 and 5 by 1 and then
increase the height of mountains 2, 3, 4 and 5 by 1. So 2 packets of power is used.