import java.util.*;
public class ListOperations
{
   //Reverse Linear Search of a RANDOM-ORDER list
   public static int reverseScan(ArrayList<Comparable> list, Comparable target)
   {
      //Base Case 1: list is empty
      if ( list.isEmpty() )
         return -1;
      
      //Base Case 2: target matches the last element  
      int highIndex = list.size() - 1;
      if ( list.get(highIndex).equals(target) )
         return highIndex;
      
      //Recursive Step: search the list without the last element   
      Comparable element = list.remove(highIndex);
      int result = reverseScan(list, target);
      list.add(element);   //replace the removed last element
      
      return result;
   }

   //Reverse Linear Search of an ASCENDING ORDER List
   public static int linearSearch(ArrayList<Comparable> list, Comparable target)
   {
      //Base Case 1: the list is empty
      if ( list.isEmpty() )
         return -1;
         
      int highIndex = list.size() - 1;
      
      //Base Case 2: target > last (biggest) element
      if ( target.compareTo( list.get(highIndex) ) > 0 )
         return -1;
         
      //Base Case 3: target matches the last element
      if ( target.compareTo( list.get(highIndex) ) == 0 )
         return highIndex;
      
      //Recursive Step: search the list without the last element   
      Comparable element = list.remove(highIndex);
      int result = linearSearch(list, target);
      list.add(element);   //replace the removed last element
      
      return result;
   }
   
   //Binary Search of an Ascending-Order List
   public static int binarySearch(ArrayList<Comparable> list, Comparable target)
   {
      return binarySearch(list, target, 0, list.size()-1);
   }
   
   private static int binarySearch(ArrayList<Comparable> list, Comparable target,
                                  int loIndex, int hiIndex)
   {
      //Base Case 1: Search range is empty
      if (loIndex > hiIndex)
         return -1;
         
      int middle = (loIndex + hiIndex) / 2;
      int comparisonResult = target.compareTo( list.get(middle) );
      
      //Base Case 2: target matches the middle element
      if ( comparisonResult == 0)
         return middle;
      
      //Recursive Step: 
      if (comparisonResult > 0)  //Search upper half of the list
         return binarySearch(list, target, middle+1, hiIndex);
      else                       //Search lower half of the list
         return binarySearch(list, target, loIndex, middle-1);
   }
   
   //Insert an item into an Ascending-Order List
   public static void insert(ArrayList<Comparable> list, Comparable item)
   {
      //Base Case 1: List is empty     
      if ( list.isEmpty() )
         list.add(item);
         
      else
      {
         int highIndex = list.size() - 1;

         //Base Case 2: item >= last (biggest) element
         if ( item.compareTo( list.get(highIndex) ) >= 0 )
            list.add(item);
            
         else  //Recursive Step: Insert into list with last element removed
         {   
            Comparable element = list.remove(highIndex);
            insert(list, item);  //Insert into the shortened list
            list.add(element);   //Replace removed last (biggest) element
         }
      }
   }
   
   //Ascending Insertion-Sort
   public static void insertionSort(ArrayList<Comparable> list)
   {
      if (list.size() > 1)
      {
         Comparable item = list.remove(0);
         insertionSort(list);
         insert(list, item);
      }
   }
   
   public static ArrayList<Comparable> copy(ArrayList<Comparable> list)
   {
      if (list.isEmpty())
         return new ArrayList<Comparable>();
         
      Comparable first = list.remove(0);
      ArrayList<Comparable> twin = copy(list);
      list.add(0, first);
      twin.add(0, first);
      return twin;
   }
   
   public static ArrayList<Comparable> merge(ArrayList<Comparable> one,
                                             ArrayList<Comparable> two)
   {
      ArrayList<Comparable> listA = copy(one);
      ArrayList<Comparable> listB = copy(two);
      
      if ( listA.isEmpty() )
         return listB;
         
      if ( listB.isEmpty() )
         return listA;
         
      Comparable firstItem = listA.get(0).compareTo(listB.get(0)) <= 0 ?
                             listA.remove(0) : listB.remove(0) ;
      ArrayList<Comparable> result = merge(listA, listB);
      result.add(0, firstItem);
      return result;
   }    
}