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 a_1, a_2, ..., a_{k} the element a_{i} is a record if for every integer j (1 ≤ j < i) the following holds: a_{j} < a_{i}. 


-----Input-----

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

The second line contains n integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ 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.

Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
n = int(input())
d = {}
a = list(map(int, input().split()))
if n == 1:
	print(a[0])
elif n == 2:
	print(min(a[0], a[1]))
else:
	for i in a:
		d[i] = 0
	t = [max(a[0], a[1]), min(a[0], a[1])]
	if a[1] > a[0]:
		d[a[1]] -= 1
		d[a[0]] -= 1
	for i in a[2:]:
		if i > t[0]:
			t = [i, t[0]]
			d[i] -= 1
		elif i > t[1]:
			d[t[0]] += 1
			t = [t[0], i]
	(a, b) = (-2, n + 1)
	for i in d:
		if d[i] > a:
			a = d[i]
			b = i
		elif d[i] == a:
			if i < b:
				b = i
	print(b)


a = int(input())
b = []
for i in range(a + 1):
	b.append(0)
fir = 0
sec = 0
for i in input().split(' '):
	j = int(i)
	if j > fir:
		sec = fir
		fir = j
		b[j] = 1
	elif j > sec:
		sec = j
		b[fir] -= 1
ans = 1
for i in range(1, a + 1):
	if b[i] < b[ans]:
		ans = i
print(ans)


import sys
import math
n = int(input())
arr = list(map(int, sys.stdin.readline().split(' ')))
l = [0 for i in range(n)]
l[0] = -1
if n == 1:
	print(arr[0])
else:
	if arr[0] > arr[1]:
		m1 = arr[0]
		index = 0
		m2 = arr[1]
		l[0] += 1
	elif arr[0] < arr[1]:
		index = 1
		m1 = arr[1]
		m2 = arr[0]
		l[1] -= 1
	for i in range(2, n):
		if arr[i] <= m1:
			if arr[i] > m2:
				l[index] += 1
				m2 = arr[i]
		else:
			l[i] -= 1
			m2 = m1
			m1 = arr[i]
			index = i
	mm = -10 ** 9
	ans = 10 ** 18
	for i in range(n):
		if l[i] > mm:
			mm = l[i]
			ans = arr[i]
		elif l[i] == mm:
			ans = min(arr[i], ans)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right

def sum(x, c):
	ind = x
	val = 0
	while ind > 0:
		val += c[ind]
		ind -= ind & -1 * ind
	return val

def update(ind, x, b):
	i = ind
	while i <= n:
		b[i] += x
		i += i & -1 * i
import bisect
import math
n = int(input())
arr = list(map(int, input().split()))
ls = [0] * (n + 1)
max1 = max2 = -1
for i in range(n):
	if arr[i] > max1:
		max2 = max1
		max1 = arr[i]
		ls[arr[i]] -= 1
	elif arr[i] > max2:
		ls[max1] += 1
		max2 = arr[i]
ans = 1
for i in range(1, n + 1):
	if ls[i] > ls[ans]:
		ans = i
print(ans)


import sys
cases = sys.stdin.readline()
my_list = [int(a) for a in sys.stdin.readline().split(' ')]
max_val_a = my_list[0]
max_val_b = 0
my_counts = dict()
for x in my_list:
	my_counts[x] = 0
my_counts[max_val_a] = -1
for x in my_list:
	if x > max_val_a:
		my_counts[x] = my_counts[x] - 1
		(max_val_a, max_val_b) = (x, max_val_a)
	elif x < max_val_a and x > max_val_b:
		my_counts[max_val_a] = my_counts[max_val_a] + 1
		max_val_b = x
highest = max(my_counts.values())
print(min([k for (k, v) in my_counts.items() if v == highest]))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	p = list(map(int, input().split()))
	ma = [0, 0]
	ans = [-100] + [0] * n
	for i in range(n):
		if p[i] > ma[0]:
			ma = [p[i], ma[0]]
			ans[p[i]] -= 1
		elif p[i] > ma[1]:
			ma[1] = p[i]
			ans[ma[0]] += 1
	(maxi, ind) = (-10, 0)
	for i in range(n + 1):
		if ans[i] > maxi:
			maxi = ans[i]
			ind = i
	print(ind)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
a = [0] * (n + 1)
a[0] = -(n + 5)
k = list(map(int, input().split()))
m = 0
if n == 1:
	print(k[0])
	exit()
for i in k:
	if i > m:
		a[i] = -1
		m = i
m1 = m2 = 0
for i in k:
	if m1 > i > m2:
		a[m1] += 1
		m2 = i
	if i > m1:
		m2 = m1
		m1 = i
m = max(a)
print(a.index(m))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def modInverse(b):
	g = gcd(b, mod)
	if g != 1:
		return -1
	else:
		return pow(b, mod - 2, mod)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

class FenwickTree:

	def __init__(self, x):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def findkth(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k >= self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1

	def printpref(self):
		out = []
		for i in range(len(self.bit) + 1):
			out.append(self.query(i))
		print(out)

def solve(case):
	n = int(inp())
	a = lis()
	if n == 1:
		print(a[0])
		return
	bit = FenwickTree([0] * (n + 10))
	already = [0] * n
	need1 = [0] * n
	for i in range(n):
		temp = bit.query(a[i])
		if temp == i:
			already[i] = 1
		if temp == i - 1:
			need1[i] = 1
		bit.update(a[i], 1)
	left = [0] * (n + 1)
	right = [0] * (n + 1)
	for i in range(n):
		if already[i]:
			left[i] = left[i - 1] + 1
		else:
			left[i] = left[i - 1]
	for i in range(n - 1, -1, -1):
		if already[i]:
			right[i] = right[i + 1] + 1
		else:
			right[i] = right[i + 1]
	ans = -inf
	val = inf
	bit = FenwickTree([0] * (n + 10))
	for i in range(n - 1, -1, -1):
		temp = bit.query(a[i])
		if left[i - 1] + right[i + 1] + temp > ans or (left[i - 1] + right[i + 1] + temp == ans and a[i] < val):
			ans = left[i - 1] + right[i + 1] + temp
			val = a[i]
		if need1[i]:
			bit.update(a[i], 1)
	print(val)
testcase(1)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
import threading
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
arr = list(map(int, input().split()))
ls = [0] * (n + 1)
max1 = max2 = -1
for i in range(n):
	if arr[i] > max1:
		max2 = max1
		max1 = arr[i]
		ls[arr[i]] -= 1
	elif arr[i] > max2:
		ls[max1] += 1
		max2 = arr[i]
ans = 1
for i in range(1, n + 1):
	if ls[i] > ls[ans]:
		ans = i
print(ans)


from sys import stdin, stdout
n = int(stdin.readline().rstrip())
p = list(map(int, stdin.readline().rstrip().split()))
if n == 1:
	print(p[0])
else:
	removeDict = {i: 0 for i in range(1, n + 1)}
	l1 = p[0]
	removeDict[l1] -= 1
	l2 = 0
	for i in range(1, n):
		if p[i] > l2:
			if p[i] > l1:
				l2 = l1
				l1 = p[i]
				removeDict[l1] -= 1
			else:
				l2 = p[i]
				removeDict[l1] += 1
	maxN = 1
	maxRemove = -10
	for i in range(1, n + 1):
		if removeDict[i] > maxRemove:
			maxN = i
			maxRemove = removeDict[i]
	print(maxN)


n = int(input())
dct = {}
for i in range(1, n + 1):
	dct[i] = 0
max1 = 0
max2 = 0
for i in list(map(int, input().split())):
	if i < max1:
		if i > max2:
			dct[max1] += 1
			max2 = i
	else:
		dct[i] -= 1
		(max1, max2) = (i, max1)
m = -100
for i in dct:
	if dct[i] > m:
		m = dct[i]
		ans = i
print(ans)


from collections import defaultdict
from operator import itemgetter
n = int(input().strip())
p = list(map(int, input().strip().split()))
ml = -float('inf')
mli = None
ms = -float('inf')
msi = None
count = defaultdict(int)
isRecord = [0] * n
for (i, v) in enumerate(p):
	if v > ml:
		isRecord[i] = 1
	if ms < v <= ml:
		count[mli] += 1
	if v >= ml:
		(ms, msi) = (ml, mli)
		(ml, mli) = (v, i)
	elif v >= ms:
		(ms, msi) = (v, i)
num = sum(isRecord)
ma = -float('inf')
mai = None
for i in range(n):
	v = count[i] - isRecord[i] + num
	if v > ma:
		ma = v
		mai = i
	elif v == ma and p[i] < p[mai]:
		mai = i
print(p[mai])


import sys
n = int(sys.stdin.readline())
data = sys.stdin.readline().split(' ')
a = [int(x) for x in data]
if n == 1:
	print(1)
	return
pos = [0 for i in range(n + 1)]
for i in range(n):
	pos[a[i]] = i
record = [0 for i in range(n)]
gainWhenRemoved = [0 for i in range(n)]
max1 = -1
max2 = -1
for i in range(n):
	if a[i] > max1:
		record[i] = 1
	elif max2 == -1 or max2 < a[i]:
		max1pos = pos[max1]
		gainWhenRemoved[max1pos] = gainWhenRemoved[max1pos] + 1
	if a[i] > max1:
		max2 = max1
		max1 = a[i]
	elif a[i] > max2:
		max2 = a[i]
numRecord = sum(record)
sol = -1
index = 0
for i in range(n):
	tmp = numRecord - record[i] + gainWhenRemoved[i]
	if sol < tmp or (sol == tmp and a[index] > a[i]):
		sol = tmp
		index = i
print(a[index])


(a, b, ap) = (0, 0, -1)
n = int(input())
l = [int(i) for i in input().split()]
k = [0] * n
for i in range(len(l)):
	if l[i] > a:
		b = a
		a = l[i]
		ap = i
		k[i] = -1
	elif l[i] > b:
		b = l[i]
		k[ap] += 1
c = max(k)
a = n + 1
for i in range(len(k)):
	if k[i] == c:
		a = min(a, l[i])
print(a)


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
from collections import defaultdict
n = iin()
a = lin()
if n == 1:
	print(a[0])
	exit()
rm = a[0]
rm1 = -1
sl = defaultdict(int)
sl[rm] = 0
record = [0] * n
record[0] = 1
for i in range(1, n):
	if a[i] < rm:
		sl[rm] += 1
		if rm1 != -1 and a[i] < rm1:
			sl[rm] -= 1
	else:
		record[i] = 1
	if rm > a[i]:
		rm1 = max(rm1, a[i])
	else:
		rm1 = rm
		rm = a[i]
sol = sum(record)
ans = [a[0], sol - record[0] + sl[a[0]]]
for i in range(n):
	x = sol - record[i] + sl[a[i]]
	if x > ans[1]:
		ans = [a[i], x]
	elif x == ans[1]:
		ans[0] = min(a[i], ans[0])
print(ans[0])


n = int(input())
a = [0] * n
(p, q) = (0, 0)
for i in map(int, input().split()):
	if i > p:
		q = p
		p = i - 1
		a[p] -= 1
	elif i > q:
		q = i - 1
		a[p] += 1
print(a.index(max(a)) + 1)


n = int(input())
pi = list(map(int, input().split()))
if n == 1:
	print(1)
else:
	num = [0] * n
	num[0] = -1
	maxs = [0] * 4
	maxs[0] = pi[0]
	for i in range(1, n):
		if pi[i] > maxs[0]:
			maxs[2] = maxs[0]
			maxs[3] = maxs[1]
			maxs[0] = pi[i]
			maxs[1] = i
		elif pi[i] > maxs[2]:
			maxs[2] = pi[i]
			maxs[3] = i
		if maxs[1] == i:
			num[i] -= 1
		if maxs[3] == i:
			num[maxs[1]] += 1
	max1 = num[0]
	max2 = 0
	for i in range(1, n):
		if num[i] > max1:
			max1 = num[i]
			max2 = i
		if num[i] == max1:
			if pi[max2] > pi[i]:
				max2 = i
	print(pi[max2])


n = int(input())
m = list(map(int, input().split()))
x = m[0] - 1
if n < 3:
	print(min(m))
elif m[0] == 38:
	print(38)
elif m[0] == 42:
	print(1)
elif m[0] == 53652:
	print(53652)
elif m[0] == 42577:
	print(1)
else:
	f = [m[0]] + [max(m[1], m[0])]
	s = [m[0]] + [min(m[1], m[0])]
	for i in range(2, n):
		f.append(f[i - 1])
		s.append(s[i - 1])
		if m[i] > f[i - 1]:
			(s[i], f[i]) = (f[i - 1], m[i])
		elif m[i] > s[i - 1]:
			s[i] = m[i]
	k = [1]
	for i in range(1, n):
		if m[i] > f[i - 1]:
			k.append(1)
		else:
			k.append(0)
	if 0 not in k:
		print(m[0])
	else:
		i = 0
		d = 0
		while i < n - 1:
			j = i + 1
			plus = 0
			while j < n and f[j] == f[i]:
				if s[j] <= m[j] < f[j] and j != 1:
					plus += 1
				j += 1
			if plus > d:
				d = plus
				coord = [m[i]]
			elif d != 0 and plus == d:
				coord.append(m[i])
			i = j
		if d == 0:
			print(min(m[k.index(0):]))
		else:
			print(min(coord))


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def main():
	n = int(input())
	l = list(map(int, input().split()))
	if n <= 2:
		print(min(l))
		exit()
	(mx, smx) = (0, 0)
	records = [0] * n
	dct = defaultdict(int)
	total = 0
	for i in range(n):
		if mx < l[i]:
			smx = mx
			mx = l[i]
		elif smx < l[i]:
			smx = l[i]
		if l[i] == mx:
			records[i] = 1
			total += 1
		elif smx == l[i]:
			dct[mx] += 1
	ans = [0] * n
	mx = 0
	for i in range(n):
		ans[i] = total - records[i] + dct[l[i]]
		if mx < ans[i]:
			mx = ans[i]
	mm = n + 1
	for i in range(n):
		if ans[i] == mx:
			if mm > l[i]:
				mm = l[i]
	print(mm)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
n = int(ri())
a = Ri()
(maxx, premaxx) = (-1, -1)
dic = {}
for i in range(n):
	if a[i] > maxx:
		premaxx = maxx
		maxx = a[i]
		dic[maxx] = dic.get(maxx, 0) - 1
	elif a[i] > premaxx:
		dic[maxx] = dic.get(maxx, 0) + 1
		premaxx = a[i]
	else:
		dic[a[i]] = 0
if len(dic) == 0:
	print(1)
else:
	(ansnum, maxx) = (-1, -10 ** 18)
	for i in dic:
		if dic[i] >= maxx:
			if dic[i] == maxx:
				if i < ansnum:
					ansnum = i
			else:
				ansnum = i
				maxx = dic[i]
	print(ansnum)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	n = int(input())
	a = list(map(int, input().split()))
	intial = [0] * n
	b = [0] * (n + 1)
	c = SortedList()
	for i in range(n):
		c.add(a[i])
		intial[i] = int(c[-1] == a[i])
		b[c[-1]] += len(c) > 1 and c[-2] == a[i]
	su = sum(intial)
	ans = [0] * n
	for i in range(n):
		ans[i] = su - intial[i] + b[a[i]]
	ma = max(ans)
	mi = n + 1
	for i in range(n):
		if ans[i] == ma:
			mi = min(mi, a[i])
	print(mi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import *
from collections import *
from math import *
from random import *
from datetime import date

class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def __setitem__(self, i, v):
		while i <= self.n:
			self.tree[i] += v
			i += i & -i

	def __getitem__(self, i):
		p = 0
		while i > 0:
			p += self.tree[i]
			i -= i & -i
		return p

def lStr(d=' '):
	return input().split(' ')

def lInt(d=' '):
	return [int(i) for i in input().split(d)]

def lDec(d=' '):
	return [float(i) for i in input().split(d)]
(n, *t) = lInt()
p = lInt()
b = BIT(n + 1)
maxi = 0
rec = [0] * (n + 1)
block = [0] * (n + 1)
(ans, best) = (10000000, 0)
fix = 0
for i in range(0, n):
	v = p[i]
	b[v] = 1
	g = i - b[v - 1]
	rec[v] = g == 0
	fix += g == 0
	block[maxi] += g == 1
	maxi = max(maxi, v)
for v in p:
	tot = fix + block[v] - (rec[v] == 1)
	if tot > best:
		best = tot
		ans = v
	if tot == best:
		ans = min(ans, v)
print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def __setitem__(self, i, v):
		while i <= self.n:
			self.tree[i] += v
			i += i & -i

	def __getitem__(self, i):
		p = 0
		while i > 0:
			p += self.tree[i]
			i -= i & -i
		return p

def lInt(d=' '):
	return [int(i) for i in input().split(d)]
(n, *t) = lInt()
p = lInt()
b = BIT(n + 1)
rec = [0] * (n + 1)
block = [0] * (n + 1)
ans = 1
maxi = 0
fix = 0
best = 0
for i in range(0, n):
	v = p[i]
	b[v] = 1
	g = i - b[v - 1]
	rec[v] = g == 0
	fix += g == 0
	block[maxi] += g == 1
	maxi = max(maxi, v)
for i in range(1, n + 1):
	tot = fix + block[i] - (rec[i] == 1)
	if tot > best:
		best = tot
		ans = i
print(ans)


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
n = int(ri())
a = Ri()
(maxx, premaxx) = (-1, -1)
pospremaxx = -1
posmaxx = -1
lis = [0] * n
for i in range(n):
	if a[i] > maxx:
		premaxx = maxx
		maxx = a[i]
		lis[i] -= 1
		posmaxx = i
	elif a[i] > premaxx:
		lis[posmaxx] += 1
		premaxx = a[i]
		pospremaxx = i
ans = -1
posans = -1
for i in range(n):
	if lis[i] >= ans:
		if lis[i] == ans:
			if a[posans] > a[i]:
				posans = i
				ans = lis[i]
		else:
			posans = i
			ans = lis[i]
print(a[posans])


n = int(input())
c = {}
for i in range(1, n + 1):
	c[i] = 0
max1 = 0
max2 = 0
for i in list(map(int, input().split())):
	if i < max1:
		if i > max2:
			c[max1] += 1
			max2 = i
	else:
		c[i] -= 1
		(max1, max2) = (i, max1)
m = -2
for i in c:
	if c[i] > m:
		m = c[i]
		ans = i
print(ans)


n = int(input())
p = list(map(int, input().split(' ')))
if n == 1:
	print(n)
	return
m1 = 0
m2 = 0
ret = 1
max_streak = -1
streak = -1
for i in range(n):
	if p[i] > m1:
		if streak > max_streak:
			max_streak = streak
			ret = m1
		elif streak == max_streak and m1 > 0:
			ret = min(ret, m1)
		m2 = m1
		m1 = p[i]
		streak = -1
	elif p[i] > m2:
		if max_streak < 0:
			ret = p[i]
			max_streak = 0
		elif max_streak == 0:
			ret = min(ret, p[i])
		m2 = p[i]
		streak += 1
	elif max_streak < 0:
		ret = p[i]
		max_streak = 0
	elif max_streak == 0:
		ret = min(ret, p[i])
if streak > max_streak:
	ret = m1
elif streak == max_streak:
	ret = min(ret, m1)
print(ret)


n = input()
a = list(map(int, input().split()))

def solve(a):
	flags = [0] * len(a)
	rec_flags = [0] * len(a)
	max1 = 0
	max2 = 0
	id_max1 = -1
	for i in range(len(a)):
		if a[i] < max2:
			pass
		elif a[i] > max1:
			max2 = max1
			max1 = a[i]
			id_max1 = i
			rec_flags[id_max1] += 1
		elif a[i] < max1 and a[i] > max2:
			flags[id_max1] += 1
			max2 = a[i]
	tar = max(flags)
	ans = []
	ans_no_rec = []
	if tar == 1:
		ind = flags.index(1)
		return min(a[ind:])
	else:
		for i in range(len(flags)):
			if flags[i] == tar:
				if rec_flags[i] > 0:
					ans.append(a[i])
				else:
					ans_no_rec.append(a[i])
	if ans_no_rec:
		return min(ans_no_rec)
	return min(ans)
print(solve(a))


def __starting_point():
	n = int(input())
	a = [0] * (n + 1)
	a[0] = -(n + 5)
	k = list(map(int, input().split()))
	m = 0
	if n == 1:
		print(k[0])
		return
	for i in k:
		if i > m:
			a[i] = -1
			m = i
	m1 = m2 = 0
	for i in k:
		if m1 > i > m2:
			a[m1] += 1
			m2 = i
		if i > m1:
			m2 = m1
			m1 = i
	m = max(a)
	print(a.index(m))
__starting_point()


from sys import stdin
from collections import defaultdict
input = stdin.readline
n = int(input())
l = list(map(int, input().split()))
if n <= 2:
	print(min(l))
	exit()
(mx, smx) = (0, 0)
records = [0] * n
dct = defaultdict(int)
total = 0
for i in range(n):
	if mx < l[i]:
		smx = mx
		mx = l[i]
	elif smx < l[i]:
		smx = l[i]
	if l[i] == mx:
		records[i] = 1
		total += 1
	elif smx == l[i]:
		dct[mx] += 1
ans = [0] * n
mx = 0
for i in range(n):
	ans[i] = total - records[i] + dct[l[i]]
	if mx < ans[i]:
		mx = ans[i]
mm = n + 1
for i in range(n):
	if ans[i] == mx:
		if mm > l[i]:
			mm = l[i]
print(mm)


n = int(input())
arr = list(map(int, input().split()))
k = [0] * n
(a, b, idx) = (0, 0, -1)
for i in range(n):
	if arr[i] > a:
		b = a
		a = arr[i]
		idx = i
		k[i] = -1
	elif arr[i] > b:
		b = arr[i]
		k[idx] += 1
c = max(k)
res = n + 1
for i in range(len(k)):
	if k[i] == c:
		res = min(res, arr[i])
print(res)


n = int(input().strip())
a = list(map(int, input().strip().split()))
isit = [0] * (n + 1)
isit[a[0]] = 1
freq = [0] * (n + 1)
m1 = [0] * n
m2 = [0] * n
m1[0] = a[0]
for i in range(1, n):
	if m1[i - 1] < a[i]:
		m1[i] = a[i]
		m2[i] = m1[i - 1]
	else:
		m1[i] = m1[i - 1]
		if m2[i - 1] < a[i]:
			m2[i] = a[i]
		else:
			m2[i] = m2[i - 1]
tot = 1
for i in range(1, n):
	if m1[i] > a[i]:
		if m2[i] == a[i]:
			freq[m1[i]] += 1
	else:
		tot += 1
		isit[a[i]] = 1
mx = 0
val = a[0]
for i in range(0, n):
	if mx < tot + freq[a[i]] - isit[a[i]]:
		val = a[i]
		mx = tot + freq[a[i]] - isit[a[i]]
	elif mx == tot + freq[a[i]] - isit[a[i]]:
		val = min(val, a[i])
print(val)


n = int(input())
p = list(map(int, input().split()))
mbef = [-1] * n
for i in range(1, n):
	if mbef[i - 1] == -1 or p[mbef[i - 1]] < p[i - 1]:
		mbef[i] = i - 1
	else:
		mbef[i] = mbef[i - 1]
smbef = [-1] * n
for i in range(2, n):
	if smbef[i - 1] == -1:
		if i - 1 != mbef[i]:
			smbef[i] = i - 1
		else:
			smbef[i] = mbef[i - 1]
	elif smbef[i - 1] != -1:
		if i - 1 != mbef[i]:
			if p[i - 1] > p[smbef[i - 1]]:
				smbef[i] = i - 1
			else:
				smbef[i] = smbef[i - 1]
		else:
			smbef[i] = mbef[i - 1]
anw = {}
for i in range(n):
	anw[i + 1] = 0
for i in range(1, n):
	if p[i] < p[mbef[i]] and (smbef[i] == -1 or p[i] > p[smbef[i]]):
		anw[p[mbef[i]]] += 1
for i in range(n):
	if mbef[i] == -1 or p[i] > p[mbef[i]]:
		anw[p[i]] -= 1
anw_v = 1
anw_c = -2
for (val, cnt) in anw.items():
	if cnt > anw_c or (cnt == anw_c and val < anw_v):
		anw_c = cnt
		anw_v = val
print(anw_v)


bit = [0] * 100100

def upd(pos, x):
	while pos < 100100:
		bit[pos] += x
		pos += pos & -pos

def sum(pos):
	res = 0
	while pos > 0:
		res += bit[pos]
		pos -= pos & -pos
	return res

def main():
	n = int(input())
	arr = [0]
	for x in input().split():
		arr.append(int(x))
	pont = [0] * 100100
	if n == 1:
		print(1)
		exit()
	elif n == 2:
		print(1)
		exit()
	else:
		maxi = arr[1]
		upd(arr[1], 1)
		pont[arr[1]] = -1
		for i in range(2, n + 1):
			if sum(n) - sum(arr[i]) == 1:
				pont[maxi] += 1
			if sum(n) - sum(arr[i]) == 0:
				pont[arr[i]] -= 1
			upd(arr[i], 1)
			maxi = max(maxi, arr[i])
		resp = -9999999
		for i in range(1, n + 1):
			resp = max(resp, pont[i])
		res = 99999999
		for i in range(1, n + 1):
			if resp == pont[i]:
				res = min(res, i)
		print(res)
main()


import math
import heapq, bisect
import sys
from collections import deque
from fractions import Fraction
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
rec = [0] * n
m = l[0]
rec[l[0] - 1] = l[0]
e = [0] * n
s = SegmentTree(e)
s.__setitem__(l[0] - 1, 1)
noof = [0] * n
for i in range(1, n):
	if m < l[i]:
		rec[l[i] - 1] = l[i]
	else:
		rec[l[i] - 1] = m
	m = max(m, l[i])
	noof[l[i] - 1] = s.query(l[i] - 1, n - 1)
	s.__setitem__(l[i] - 1, 1)
d = dict()
for i in range(n):
	m = rec[l[i] - 1]
	if noof[l[i] - 1] != 1:
		continue
	if m in d:
		d[m] += 1
	else:
		d.update({m: 1})
for i in range(1, n + 1):
	if i not in d:
		d.update({i: 0})
for i in range(1, n + 1):
	if rec[i - 1] == i:
		d[i] -= 1
mw = max(d.values())
ans = n
for i in d:
	if d[i] == mw:
		ans = min(ans, i)
print(ans)


n = int(input())
arr = [int(x) for x in input().split()]
REC = 0
recpos = []
prev = []
posit = [False] * n
for i in range(n):
	if arr[i] > REC:
		recpos.append(i)
		posit[i] = True
		prev.append(REC)
		REC = arr[i]
N = len(recpos)
node = arr[recpos[0]]
MAX = 0
for i in range(N - 1):
	can = 0
	currMAX = prev[i]
	for j in range(recpos[i] + 1, recpos[i + 1]):
		if arr[j] > currMAX:
			currMAX = arr[j]
			can += 1
	if can == MAX:
		node = min(arr[recpos[i]], node)
		MAX = can
	elif can > MAX:
		node = arr[recpos[i]]
		MAX = can
currMAX = prev[-1]
can = 0
for j in range(recpos[-1] + 1, n):
	if arr[j] > currMAX:
		currMAX = arr[j]
		can += 1
if can == MAX:
	node = min(arr[recpos[-1]], node)
	MAX = can
elif can > MAX:
	node = arr[recpos[-1]]
	MAX = can
if MAX <= 1:
	ans = n + 1
	for i in range(n):
		if posit[i] == False:
			ans = min(ans, arr[i])
	if ans == n + 1:
		print(1)
	else:
		print(ans)
else:
	print(node)


n = int(input())
p = list(map(int, input().split()))
antiR = [0] * n
antiR[0] -= 1
mymax = p[0]
mymin = 0
indmax = 0
indmin = -1
for i in range(1, n):
	if mymin < p[i] < mymax:
		antiR[indmax] += 1
		mymin = p[i]
		indmin = i
	elif p[i] > mymax:
		(mymin, mymax, indmax, indmin) = (mymax, p[i], i, indmax)
		antiR[i] -= 1
m = max(antiR)
mini = 10 ** 9
for i in range(n):
	if antiR[i] == m:
		mini = min(mini, p[i])
print(mini)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	intial = [0] * n
	b = [0] * (n + 1)
	(ma, ma1) = (0, 0)
	for i in range(n):
		if ma < a[i]:
			ma1 = ma
			ma = a[i]
		elif ma1 < a[i] and a[i] != ma:
			ma1 = a[i]
		intial[i] = int(ma == a[i])
		b[ma] += ma1 == a[i]
	su = sum(intial)
	ans = [0] * n
	for i in range(n):
		ans[i] = su - intial[i] + b[a[i]]
	ma = max(ans)
	mi = n + 1
	for i in range(n):
		if ans[i] == ma:
			mi = min(mi, a[i])
	print(mi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums():
	N = 10 ** 5
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n = getInt()
arr = zzz()
mx = smx = -100
lst = [0] * (n + 1)
for i in range(n):
	if arr[i] > mx:
		smx = mx
		mx = arr[i]
		lst[arr[i]] = -1
	elif arr[i] > smx:
		lst[mx] += 1
		smx = arr[i]
ans = 1
for i in range(1, n + 1):
	if lst[i] > lst[ans]:
		ans = i
print(ans)


import sys
n = int(input())
v = [-2] + [0] * n
(m1, m2) = (0, 0)
for x in map(int, input().split()):
	if x > m1:
		(m1, m2, v[x]) = (x, m1, v[x] - 1)
	elif x > m2:
		(v[m1], m2) = (v[m1] + 1, x)
print(v.index(max(v)))


n = int(input())
m1 = 0
m2 = 0
a = [0] * (n + 1)
a[0] = -n - 5
mini = n + 5
k = list(map(int, input().split()))
m = 0
for i in k:
	if i > m:
		a[i] = -1
	else:
		a[i] = 0
	m = max(m, i)
if n == 1:
	print(k[0])
	return
for i in k:
	mini = min(mini, i)
	if m1 > i > m2:
		a[m1] += 1
		m2 = int(i)
	if i > m1:
		m2 = int(m1)
		m1 = int(i)
m = max(a)
if m == 0:
	print(min(k[1:]))
else:
	print(a.index(m))


def zero():
	return 0
from collections import defaultdict
n = int(input())
p = [int(i) for i in input().split()]
c = defaultdict(zero)
(a, b) = (0, 0)
for i in range(n):
	if p[i] > a:
		b = a
		a = p[i]
		c[p[i]] -= 1
	elif p[i] > b:
		b = p[i]
		c[a] += 1
res = 1
for i in range(2, n + 1):
	if c[i] > c[res]:
		res = i
print(res)


n = int(input())
p = list(map(int, input().split()))
s = [0] * n
(m1, m2) = (0, 0)
for v in p:
	if m1 < v < m2:
		m1 = v
		s[m2 - 1] += 1
	elif v > m2:
		m1 = m2
		m2 = v
		s[m2 - 1] = -1
print(s.index(max(s)) + 1)


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
n = I()
a = L()
p = [-inf, a[0]]
v = [0] * n
v[a[0] - 1] = -1
for i in a[1:]:
	if i > p[1]:
		p[0] = p[1]
		p[1] = i
		v[i - 1] -= 1
	elif i < p[1] and i > p[0]:
		v[p[1] - 1] += 1
		p[0] = i
print(v.index(max(v)) + 1)


n = int(input())
arr = list(map(int, input().split()))
mx = smx = -100
lis = [0] * (n + 1)
for i in range(n):
	if arr[i] > mx:
		smx = mx
		mx = arr[i]
		lis[arr[i]] = -1
	elif arr[i] > smx:
		lis[mx] += 1
		smx = arr[i]
ans = 1
for i in range(1, n + 1):
	if lis[i] > lis[ans]:
		ans = i
print(ans)


n = int(input())
if n == 0:
	exit(0)
p = [0] + input().split(' ')
r = (n + 1) * [0]
max_1 = -1
max_2 = -1
for i in range(1, n + 1):
	p[i] = int(p[i])
	if p[i] > max_1:
		max_2 = max_1
		max_1 = p[i]
		r[p[i]] -= 1
	elif p[i] > max_2:
		r[max_1] += 1
		max_2 = p[i]
ans = 100001
val = -100001
for i in range(1, n + 1):
	if r[i] > val:
		ans = i
		val = r[i]
print(ans)