phoxis

import java.io.*;
import java.util.Scanner;
import java.lang.Thread;
import java.util.Random;

class mergeSort
{
  static void merge (int arr[], int low, int mid, int high)
  {
	int buf1[], buf2[];
	int n1 = mid - low + 1, n2 = high - mid;
	int j, i1, i2;

	if (Runtime.getRuntime (). freeMemory () < ((n1 + n2) * 4))
	  Runtime.getRuntime (). gc ();
	buf1 = new int [n1];
	buf2 = new int [n2];

	for (i1=0, j=low; i1<n1; i1++, j++)
	  buf1[i1] = arr[j];

	for (i2=0, j=mid+1; i2<n2; i2++, j++)
	  buf2[i2] = arr[j];

	for (i1=0, i2=0, j=low; (i1<n1) && (i2<n2); j++)
	{
	  if (buf1[i1] < buf2[i2])
		arr[j] = buf1[i1++];
	  else
		arr[j] = buf2[i2++];
	}
	while (i1 < n1)
	  arr[j++] = buf1[i1++];
	while (i2 < n2)
	  arr[j++] = buf2[i2++];
  }

  static void sort (int arr[], int low, int high)
  {
	if (low < high)
	{
	  int mid = (high + low)/2;
	  sort (arr, low, mid);
	  sort (arr, mid + 1, high);
	  merge (arr, low, mid, high);
	}
  }
}

class multiThreadMergeSortThreads extends mergeSort implements Runnable
{
  int arr[], init_low, init_high;

  multiThreadMergeSortThreads (int init_arr[], int low, int high)
  {
	arr = init_arr;
	init_low = low;
	init_high = high;
  }

  public void run ()
  {
	  mergeSort.sort (arr, init_low, init_high);
// 	  System.out.print ("[#" + init_low + "," + init_high + "] ");
  }
}

class multiThreadMergeSort
{
  static Thread t[];
  static multiThreadMergeSortThreads ob[];
  static int threads, i;

  static void mtSort (int arr[], int low, int high, int tno)
  {
	int size = (int) Math.ceil ((double)arr.length/(double)tno), low_index = low, high_index, mid_index;
	threads = tno;
	t = new Thread [threads];
	ob = new multiThreadMergeSortThreads [threads];

	for (i=0; i<threads; i++)
	{
	  high_index = low_index + size - 1;
	  if (high_index > high)
	  {
		high_index = high;
	  }
	  ob[i] = new multiThreadMergeSortThreads (arr, low_index, high_index);
	  t[i] = new Thread (ob[i]);
	  low_index = high_index + 1;
	}
	for (i=0; i<threads; i++)
	{
	  t[i].start ();
	}

	for (i=0; i<threads; i++)
	{
	  try
	  {
		t[i].join ();
	  }
	  catch (InterruptedException e)
	  {
	  }
	}

	while (size < arr.length)
	{
	  for (low_index = low, i=0; low_index < high;)
	  {
		mid_index = low_index + size - 1;
		high_index = mid_index + size;
		if (high_index > high)
		  high_index = high;
		mergeSort.merge (arr, low_index, mid_index, high_index);
// 		System.out.print ("\n(" + low_index + "," + mid_index + "," + high_index + "):(" + size + ")");
		low_index = high_index + 1;
	  }
	  size = size * 2;
	}
  }
}


class mergeSortTest
{
  public static void main (String args[])
  {
	Scanner sc = new Scanner (System.in);
	Random rand = new Random ();
	System.out.print ("\nEnter n: ");

	int n = sc.nextInt ();
	int arr[] = new int [n];

	for (int i=0; i<n; i++)
	{
	  arr[i] = rand.nextInt ();
// 	  arr[i] = sc.nextInt ();
	}

// 	System.out.print ("\n\n");
// 	for (int i=0; i<n; i++)
// 	{
// 	  System.out.print ("[" + arr[i] + "] ");
// 	}
// 	System.out.print ("\n\n");
// 	mergeSort.sort (arr, 0, arr.length - 1);
	multiThreadMergeSort.mtSort (arr, 0, arr.length - 1, 4);

	boolean flag = true;
	for (int i=0; i<n-1; i++)
	{
	  if (arr[i] > arr[i+1])
	  {
		flag = false;
	  }
// 	  System.out.print ("[" + arr[i] + "] ");
	}
	if (flag == true)
	{
	  System.out.print ("\n[SUCCESS]");
	}
	else
	{
	  System.out.print ("\n[FAILED]");
	}
	System.out.print ("\n\n");
  }
}