import java.util.Scanner;
import java.io.*;

/*
 * Lab 5
 *
 * Author: Robin Dawes
 *
 * Date: 20081023
 *
 * Comment: 
 *
 */

public class Stocks {

    static int instances;
    static int numOfDays;
    static int[] prices;

 
    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_5_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            System.out.print("\nInstance " + i + " input: ");
            numOfDays = myScanner.nextInt();
            prices = new int[numOfDays];
            if (numOfDays == 1) System.out.println("Only one day of data provided - cannot buy and sell on the same day");
            else {
                for (int d = 0; d < numOfDays; d++){
                    prices[d] = myScanner.nextInt();
                    System.out.print(prices[d] + "  ");
                }
            }
            System.out.println();
            DayPair solution = findBest(0,numOfDays-1);
            System.out.println("Optimal solution : Buy on day " + solution.getStart() +
                                " and sell on day " + solution.getFinish() + " for a profit of " + solution.getProfit());
        }
    }
    
    
    static DayPair findBest(int s, int f)  {
        DayPair LS, RS, CS, Sol;
        if (s >= f) {
            System.out.println("Error in findBest");
            return new DayPair(-1,-1,-1);
        }
        else if (s+1 == f) 
            return new DayPair(s,f,prices[f] - prices[s]);
        else {
            int m = (s+f)/2;
            RS = findBest(m,f);
            CS = findCross(s,m,f);
            if (RS.getProfit() > CS.getProfit()) Sol = RS;
            else Sol = CS;
            if (s+1 != m) {
                LS = findBest(s, m-1);
                if (LS.getProfit() > Sol.getProfit()) Sol = LS;
            }
            return Sol;            
        }
    }
    
    static DayPair findCross(int s, int m, int f) {
        int leftMin = findMin(s, m-1);
        int rightMax = findMax(m, f);
        return new DayPair(leftMin, rightMax, prices[rightMax] - prices[leftMin]);
    }
    
    static int findMin(int a, int b) {
        if (a > b) {
            System.out.println("Error in findMin");
            return -1;
        }
        else if (a == b) return a;
        else {
            int m = (a+b)/2;
            int lm = findMin(a,m);
            int rm = findMin(m+1,b);
            if (prices[lm] <= prices[rm]) return lm;
            else return rm;
        }
    }
    
    static int findMax(int a, int b) {
        if (a > b) {
            System.out.println("Error in findMax");
            return -1;
        }
        else if (a == b) return a;
        else {
            int m = (a+b)/2;
            int lm = findMax(a,m);
            int rm = findMax(m+1,b);
            if (prices[lm] >= prices[rm]) return lm;
            else return rm;
        }
    }

}