StockMaximize

Your algorithms have become so good at predicting the market that you now know what the share price

 of Wooden Orange Toothpicks Inc. (WOT) will be for the next N days.

Each day, you can either buy one share of WOT, or sell any number of shares of WOT that you own. 

What is the maximum profit you can obtain with an optimum trading strategy?

Input

The first line contains the number of test cases T. T test cases follow:

The first line of each test case contains a number N. The next line contains N integers, denoting the 

predicted price of WOT shares for the next N days.

Output

Output T lines, containing the maximum profit which can be obtained for the corresponding test case.

Constraints

1 <= T <= 10
1 <= N <= 50000

All share prices are between 1 and 100000

Sample Input

3
3
5 3 2
3
1 2 100
4
1 3 1 2
Sample Output

0
197
3
Explanation

For the first case, you cannot obtain any profit because the share price never rises. 

For the second case, you can buy one share on the first two days, and sell both of them on the third day.

/*
 *  StockMax.c
 *  InterviewStreet
 *
 *  Created by Kyle Donnelly on 3/5/13.
 *
 * Pretty straightforward solution:
 *  Basically, you want to own as many shares as possible on the day
 *   that stock is worth the most
 *   Because any price you could have bought it for previously
 *   is less than it is now.
 *  After that day when it's worth the most, just repeat the process.
 *
 * We keep an array of prices
 *  and an array of indexes associated with the sorted price array
 * Step through those indexes in descending order
 *  Buy every day since the last peak in price
 *  simple formula: (this peak index - last peak index) * price of this peak
 *  then subtract the amount of money it would have cost to buy at all the earlier prices.
 *
 * Space complexity:
 *  We need two arrays of length 'n' --> O(n)
 *
 * Running time complexity:
 *  Sorting array of length 'n' with quicksort --> O(n*logn)
 *  Look through each index in decreasing order (look for highest peaks in remaining prediction)
 *   Step through each price until that peak --> O(n)
 *  so O(n*logn) overall, sorting is the bottleneck.
 *
 * Don't have to worry about the order peaks are sorted in if they have the same value
 *  selling everything or buying that share and selling it later have the exact same effect
 *
 */

#include 
#include 

typedef unsigned int uint;

/*
 * Permutes array idx so that the array indexers correspond
 *    to a sorted order of the array
 *    but the array is not actually changed.
 */
static void q_sort (uint *arr, uint *idx, uint beg, uint end) {
 if (end > beg + 1)
 {
  uint piv = arr[idx[(end+beg)/2]], l = beg, r = end-1;
  while (l <= r)
  {
   if (arr[idx[l]] > piv)
    l++;
   else if (arr[idx[r]] < piv)
    r--;
   else {
    uint t = idx[l];
    idx[l++] = idx[r];
    idx[r--] = t;
   }
  }
  q_sort(arr, idx, beg, r+1);
  q_sort(arr, idx, l, end);
 }
 return;
}

int main (void) {
 uint cases, days, *prices, *idx;
 uint best_price, last_index;
 
 scanf("%u", &cases);
 
 for (uint i=0; i  scanf("%u", &days);
  prices = malloc(sizeof(uint) * days);
  idx = malloc(sizeof(uint)*days);
  best_price = last_index = 0;
  
  for (uint j=0; j   scanf("%u", &(prices[j]));
   idx[j] = j;
  }
  
  q_sort(prices, idx, 0, days);
  
  for (uint j=0; j   if (idx[j] >= last_index) {
    best_price += prices[idx[j]] * (idx[j] - last_index);
    for (uint k=last_index; k     best_price -= prices[k];
    }
    last_index = idx[j] + 1;
   }
  }
  
  printf("%u\n", best_price);
  free(prices);
  free(idx);
 }
 
 return 0;
}