import java.util.Arrays;
import java.util.Scanner;

public class FindPairs {
	public void findPairsBruteForce(int[] input, int target) {
		/* TODO */
	}
	public void findPairsImproved(int[] input, int target) {
		mergeSort(input); // O(n log n) sort given to you
		// Efficiency should be better than the brute force algorithm!
	}
	private void mergeSort(int[] arr) { mergeSort(arr, 0, arr.length - 1); }
	private void mergeSort(int[] arr, int low, int high) {
		if (low >= high) return;
		int mid = (low + high) / 2; // tends to give the left index
		mergeSort(arr, low, mid);
		mergeSort(arr, mid + 1, high);
		merge(arr, low, mid, high);
	}
	private void merge(int[] arr, int low, int leftLast, int high) {
		int leftIdx = low; // arr[low .. leftLast]
		int rightIdx = leftLast + 1; // arr[leftLast + 1 .. high]
		int bufferIdx = 0;
		int[] buffer = new int[high - low + 1];
		while (leftIdx <= leftLast && rightIdx <= high)
			if (arr[leftIdx] <= arr[rightIdx])
				buffer[bufferIdx++] = arr[leftIdx++];
			else
				buffer[bufferIdx++] = arr[rightIdx++];
		while (leftIdx <= leftLast)
			buffer[bufferIdx++] = arr[leftIdx++];
		while (rightIdx <= high)
			buffer[bufferIdx++] = arr[rightIdx++];
		leftIdx = low;
		bufferIdx = 0;
		while (leftIdx <= high)
			arr[leftIdx++] = buffer[bufferIdx++];
	}

	public static void main(String[] args) {
		Scanner objScanner = new Scanner(System.in);
		System.out.print("Enter size of array: ");
		int len = objScanner.nextInt();
		int[] arr = new int[len];
		System.out.print("Enter the elements: ");
		for (int idx = 0; idx < arr.length; idx++)
			arr[idx] = objScanner.nextInt();
		System.out.print("Enter the value of k: ");
		FindPairs algo = new FindPairs();
		int k = objScanner.nextInt();
		algo.findPairsBruteForce(arr, k);
		algo.findPairsImproved(arr, k);
		objScanner.close();
	}	
}