import java.util.Scanner;

public class Stocks {
	
	public static void testStcks() {
		Stocks r = new Stocks();
		int[] numbers = new int[] {2,2,10,2,5,7,1,4,9,0};
		
		//[1,2,4,2,5,7,2,4,9,0]  13
		
		var rec = r.maxProfitDiff(numbers, 1);
		System.out.println(rec + "!");
		
		
		
	}

	
    public static void simpleMaxStock() {
	    Scanner sc = new Scanner(System.in);
	    int numOfTestCase = sc.nextInt();
	    for (int i = 0; i < numOfTestCase; i++) {
	      int n = sc.nextInt();
	      
	      int[] stockPrice = new int[n];
	      for (int j = 0; j < n; j++) 
	        stockPrice[j] = sc.nextInt();
	      
	      // Start traversing
	      long profit = 0;
	      int currMax = Integer.MIN_VALUE;
	      for (int j = n - 1; j >= 0; j--) {
	        if (currMax < stockPrice[j]) {
	          currMax = stockPrice[j];
	        }
	        profit += (currMax - stockPrice[j]);
	      }
	      System.out.println(profit);  

	    }
	    sc.close();
	  } 
    
	  public int maxProfit(int[] prices) {
		  // Leetcode #121
		  // single day to buy one stock and choosing a 
		  // different day in the future to sell that stock.
		  
		  if(prices == null || prices.length <2) return 0;
		  
		  int profit = 0, tProfit = 0;
		  int currMax = Integer.MIN_VALUE;
		  
		  for(int i = prices.length-1; i>=0; i--) {
			  if(currMax < prices[i]) currMax = prices[i];
			  tProfit = currMax - prices[i];
			  if(tProfit > profit) profit = tProfit;			  
		  }	  
		  
		  
		  return profit;  
		  
	  }
	
	  
	  public int maxProfit2(int[] prices) {
		  // Leetcode #122
		  // One share on hand at a time
		  // Buy and sell several times
		  
		  if(prices == null || prices.length <2) return 0;
		  
		  int profit = 0;
		  for(int i = prices.length-2; i>=0; i--) {
			  if(prices[i] < prices[i+1]) profit += prices[i+1] - prices[i];
		  }	  
		  
		  
		  return profit;  
		  
	  }	  
	  
	  public int maxProfit3(int[] prices) {
		  // Leetcode #123
		  // One share on hand at a time
		  // Buy and sell two times at most
		  
		  if(prices == null || prices.length <2) return 0;
		  
		  // 1,2,4,2,5,7,2,4,9,0
		  
		  int firstSell = 0;
		  int secondSell = 0;
		  int firstBuy = Integer.MAX_VALUE;
		  int secondBuy = Integer.MAX_VALUE;
		  for(int i = 0; i < prices.length; i++) {
		    int p = prices[i];									//5
		    firstBuy = Math.min(firstBuy, p);					//1
		    firstSell = Math.max(firstSell, p - firstBuy);		//4
		    secondBuy = Math.min(secondBuy, p - firstSell);		//-1
		    secondSell = Math.max(secondSell, p - secondBuy);	//6
		  }
		  
		  return secondSell;  
		  
	  }		  

	  
	  public int maxProfitDiff(int[] prices, int diff) {
		  // Maximum stock profit: return the maximum profit 
		  // assuming that you can only buy and sell once
		  // and the difference between buy and sell time 
		  // must be at least five seconds long (or one second)
		  
		  if(prices == null || prices.length < diff+1) return 0;
		  
		  // 1,2,4,2,5,7,2,4,9,0
		  
		  int profit = 0, tProfit =0;
		  		  
		  int currMax = Integer.MIN_VALUE;
		  int maxPos = 0;
		  
		  for(int i = prices.length-1; i>=0; i--) {
			  if(currMax < prices[i] && i > diff) {
				  currMax = prices[i];
				  maxPos = i;
			  }
			  if(maxPos - i > diff ) tProfit = currMax - prices[i];
			  if(tProfit > profit) profit = tProfit;	
			  
			  System.out.println("out:"+i+" "+currMax+" "+tProfit);
		  }	 		  
		  
		  return profit;  
		  
	  }		  
	  
	  
	
}