You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai. 

Input

The first line contains the only integer n (1 ≤ n ≤ 105) — the length of the permutation.

The second line contains n integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation. All the integers are distinct.

Output

Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

Examples

Input

1
1


Output

1


Input

5
5 1 2 3 4


Output

5

Note

In the first example the only element can be removed.
import java.util.*;
import java.io.*;

public class File {
	
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				}
				catch (IOException e) {
					e.printStackTrace();
				}
			}
			
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
	}	
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		
		
		
		
		int n = sc.nextInt();
		int[] p = new int[n];
		
		for (int i = 0; i < n; i++) {
			p[i] = sc.nextInt();
		}
		
		// Can only remove 1 element.
		if (n == 1) {
			out.println(1);
			out.close();
			return;
		}
		
		// O(N^2):
		// We can try removing each element, and counting how many records of the remaining elements.
		
		// When there is an element to the left greater, right away it cannot be a record.
		// Can keep a monotonically increasing queue of elements from left to right.
		
		
		// Slide to the left, 1 index at a time.
		// Keep a queue of monotonically increasing element of right side elements.
		
		// Precompute all records to left of each index.
		
		
		// Number of records up, and including, this index.
		int[] recordsToLeft = new int[n];
		LinkedList<Integer> queue = new LinkedList<>();
				
		for (int i = 0; i < n; i++) {
			int val = p[i];
			
			if (queue.isEmpty()) {
				queue.addLast(val);
			}
			else {
				if (queue.getLast() < val) {
					queue.addLast(val);
				}
			}
			
			// Queue will only contain records.
			recordsToLeft[i] = queue.size();
		}
		
		// Store the max element to the left of, and including, this index.
		int[] maxToLeft = new int[n];
		maxToLeft[0] = p[0];
		for (int i = 1; i < n; i++) {
			maxToLeft[i] = Math.max(maxToLeft[i-1], p[i]);
		}
		
		
		int maxRecords = 0;
		int removeElement = p[0];
		
		// Queue of increasing elements. Must all be records.
		queue.clear();
		
		// Remove each element 1 at a time.
		for (int i = n-1; i >= 0; i--) {
			// Calculate records without this element yet.
			int maxLeft = i > 0 ? maxToLeft[i-1] : 0;
			int recordsRight = queue.size() - binarySearch(queue, maxLeft);
			int recordsLeft = i > 0 ? recordsToLeft[i-1] : 0;
			int total = recordsLeft + recordsRight;
			
			if (total > maxRecords) {
				maxRecords = total;
				removeElement = p[i];
			}
			else if (total == maxRecords) {
				removeElement = Math.min(removeElement, p[i]);
			}
			
			// Add this element to the queue.
			int val = p[i];
			
			while (!queue.isEmpty() && val >= queue.getFirst()) {
				queue.removeFirst();
			}
			
			queue.addFirst(val);
		}
		
		out.println(removeElement);
		
		out.close();
	}
	
	// Binary search in the queue to find leftmost element > the target
	public static int binarySearch(LinkedList<Integer> queue, int target) {
		int res = queue.size();
		
		int lo = 0;
		int hi = queue.size()-1;
		
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			
			if (queue.get(mid) > target) {
				res = Math.min(res, mid);
				hi = mid - 1;
			}
			else {
				lo = mid + 1;
			}
		}
		
		return res;
	}
}




