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: interview

Starter code:

Solutions:
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())
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)

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(count)
print(p[mai])

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
  else:
    if 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=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())
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])


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)

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())
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)



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

    # max1 > max2

    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))

import sys

cases = sys.stdin.readline()
my_list = [int(a) for a in sys.stdin.readline().split(" ")]
#my_list = [4, 5, 3, 2, 1]

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:
  #print(my_counts)
  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
    
#print(my_counts)
highest = max(my_counts.values())
print(min([k for k, v in my_counts.items() if v == highest]))

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)
  




def llist(n):
  return [0 for i in range(0, n)]

class BIT:
  def __init__(self, n):
  
    self.n = n  
    self.tree = llist(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 = llist(n+1); block = llist(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)
  




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

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



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)
		return
	elif n == 2:
		print(1)
		return
	else:
		
		maxi = arr[1]
		upd(arr[1],1)
		pont[arr[1]] = -1

		for i in range(2,n+1):
			'''	
			print("sum[",n,"] = ",sum(n))
			print("sum[",arr[i],"] = ",sum(arr[i]))
			print()
			'''

			if (sum(n) - sum(arr[i])) == 1:
				#se eu tirar consigo 1
				pont[maxi] += 1
			if (sum(n) - sum(arr[i])) == 0:
				#se eu tirar perco 1
				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):
			#	print(i, ": ", pont[i])
			if resp == pont[i]:
				res = min(res, i)	

		print(res)

main()


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))

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(v, m1, m2, max(s))
print(s.index(max(s))+1)

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 __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()

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
    else:
        if (max2 == -1 or max2 < a[i]):
            max1pos = pos[max1]
            gainWhenRemoved [max1pos] = gainWhenRemoved [max1pos] + 1

    if (a[i] > max1):
        max2 = max1
        max1 = a[i]
    else:
        if (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])

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())
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)

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)))