import java.util.*;
public class SecondMin {

	private static int findMin(int[] arr, int start, int end, Map<Integer, List<Integer>> map) {
		
		if(end-start<=1)
			return arr[start];
		if(end-start==2) {
			if(arr[end-1] < arr[start]) {
				map.get(arr[end-1]).add(arr[start]);
				return arr[end-1];
			}else{
				map.get(arr[start]).add(arr[end-1]);
				return arr[start];
			}
		}else{
			int minLeft = findMin(arr, start, (end+start)/2, map);
			int minRight = findMin(arr, (end+start)/2, end, map);
			
			if(minLeft < minRight) {
				map.get(minLeft).add(minRight);
				return minLeft;
			}else{
				map.get(minRight).add(minLeft);
				return minRight;
			}
		}
	}

	public static int findSecondMin(int[] arr) throws Exception {
		if(arr.length < 2)
			throw new Exception();
		
		Map<Integer, List<Integer>> map = new HashMap<>();
		
		for(int x : arr)
			map.put(x, new ArrayList<>());
		int min = findMin(arr, 0, arr.length, map);
		
		int second = map.get(min).get(0);

		for(int x : map.get(min))
			if(x < second)
				second = x;
		return second;
	}

	public static void main(String[] args) throws Exception {
		Random r = new Random();

		int[] arr = new int[10];

		for(int i=0; i<10; i++)
			arr[i] = r.nextInt(50);
		
		System.out.println(Arrays.toString(arr));

		System.out.println(findSecondMin(arr));
	}
}