For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For $n$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $k$ that if the shark in some day traveled the distance strictly less than $k$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $k$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $k$.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of $n$ days we can find consecutive nonempty segments when the shark traveled the distance less than $k$ in each of the days: each such segment corresponds to one location. Max wants to choose such $k$ that the lengths of all such segments are equal.

Find such integer $k$, that the number of locations is as large as possible. If there are several such $k$, print the smallest one.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of days.

The second line contains $n$ distinct positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the distance traveled in each of the day.


-----Output-----

Print a single integer $k$, such that   the shark was in each location the same number of days,  the number of locations is maximum possible satisfying the first condition,  $k$ is smallest possible satisfying the first and second conditions. 


-----Examples-----
Input
8
1 2 7 3 4 8 5 6

Output
7
Input
6
25 1 2 3 14 36

Output
2


-----Note-----

In the first example the shark travels inside a location on days $1$ and $2$ (first location), then on $4$-th and $5$-th days (second location), then on $7$-th and $8$-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the $2$-nd day, so there is only one location.

Difficulty: HARD
Tags: Tree algorithms

Data structures

Spanning trees

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
def union(x, y, a, each):
	x1 = x
	y1 = y
	while a[x] > 0:
		x = a[x]
	while a[y] > 0:
		y = a[y]
	each[-1 * a[x]] -= 1
	each[-1 * a[y]] -= 1
	each[-1 * (a[x] + a[y])] += 1
	if a[x] > a[y]:
		a[y] += a[x]
		a[x] = y
		res = y
	else:
		a[x] += a[y]
		a[y] = x
		res = x
	while x1 != x:
		temp = x1
		x1 = a[x1]
		a[temp] = res
	while y1 != y:
		temp = y1
		y1 = a[y1]
		a[temp] = res

def find(x, y, a):
	x1 = x
	y1 = y
	while a[x] > 0:
		x = a[x]
	while a[y] > 0:
		y = a[y]
	ans = False
	if y == x:
		ans = True
	while y1 != y:
		temp = a[y1]
		a[y1] = y
		y1 = temp
	while x1 != x:
		temp = a[x1]
		a[x1] = x
		x1 = temp
	return ans

def getsize(x, par):
	x1 = x
	while par[x] > 0:
		x = par[x]
	ans = -1 * par[x]
	while x != x1:
		temp = par[x1]
		par[x1] = x
		x1 = temp
	return ans
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = [a[i], i]
a.sort()
par = [-2.1 for i in range(n + 1)]
max1 = 0
maxk = a[0][0] - 1
numloc = 0
each = [0 for i in range(n + 1)]
i = 0
while i < n:
	curk = a[i][0]
	while i < n and a[i][0] == curk:
		loc = a[i][1]
		if loc == 0:
			par[0] = -1
			numloc += 1
			each[1] += 1
			if par[1] != -2.1:
				numloc -= 1
				union(0, 1, par, each)
		elif loc == n - 1:
			par[n - 1] = -1
			numloc += 1
			each[1] += 1
			if par[n - 2] != -2.1:
				numloc -= 1
				union(n - 1, n - 2, par, each)
		else:
			numloc += 1
			each[1] += 1
			par[loc] = -1
			if par[loc - 1] != -2.1:
				union(loc, loc - 1, par, each)
				numloc -= 1
			if par[loc + 1] != -2.1:
				union(loc, loc + 1, par, each)
				numloc -= 1
		i += 1
	if each[getsize(loc, par)] == numloc:
		if numloc > max1:
			maxk = curk
			max1 = numloc
print(maxk + 1)


BigNum = 10 ** 10
n = int(input())
aa = [BigNum] + list(map(int, input().split(' '))) + [BigNum]
appear = sorted([(v, i) for (i, v) in enumerate(aa)])
ans = -1
maxLocations = 0
intervals = [(i, i) for i in range(len(aa))]
lengths = {}

def incCount(val):
	nonlocal lengths
	lengths[val] = lengths.get(val, 0) + 1

def decCount(val):
	nonlocal lengths
	if lengths[val] == 1:
		del lengths[val]
	else:
		lengths[val] -= 1

def mergeIntervals(a, b):
	return (min(a[0], b[0]), max(a[1], b[1]))
for (v, i) in appear:
	if v == BigNum:
		continue
	inter = intervals[i]
	if aa[i - 1] < aa[i]:
		li = intervals[i - 1]
		decCount(li[1] - li[0] + 1)
		inter = mergeIntervals(li, inter)
	if aa[i] > aa[i + 1]:
		ri = intervals[i + 1]
		decCount(ri[1] - ri[0] + 1)
		inter = mergeIntervals(ri, inter)
	intervals[inter[0]] = inter
	intervals[inter[1]] = inter
	incCount(inter[1] - inter[0] + 1)
	if len(lengths) == 1:
		count = list(lengths.values())[0]
		if count > maxLocations:
			maxLocations = count
			ans = v + 1
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)
n = int(input())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b.sort(key=lambda x: x[0])
group_cnt = [0] * (n + 1)
ans = 0
uf = UnionFind(n)
segment_count = 0
for (add_count, (value, index)) in enumerate(b):
	group_cnt[1] += 1
	if index > 0:
		if a[index - 1] < value:
			if uf.same(index - 1, index) == False:
				(size_l, size_r) = (uf.size(index - 1), uf.size(index))
				group_cnt[size_l] -= 1
				group_cnt[size_r] -= 1
			uf.union(index - 1, index)
			size_new = uf.size(index)
			group_cnt[size_new] += 1
	if index < n - 1:
		if a[index + 1] < value:
			if uf.same(index, index + 1) == False:
				(size_l, size_r) = (uf.size(index), uf.size(index + 1))
				group_cnt[size_l] -= 1
				group_cnt[size_r] -= 1
			uf.union(index, index + 1)
			size_new = uf.size(index)
			group_cnt[size_new] += 1
	size_new = uf.size(index)
	if group_cnt[size_new] * size_new == add_count + 1:
		if segment_count < group_cnt[size_new]:
			ans = value + 1
			segment_count = group_cnt[size_new]
print(ans)


class Union:

	def __init__(self, n):
		self.p = {i: i for i in range(n)}
		self.rank = {i: 1 for i in range(n)}

	def find(self, x):
		if x < 0:
			return x
		if self.p[x] != x:
			self.p[x] = self.find(self.p[x])
		return self.p[x]

	def union(self, x, y):
		if x < 0 or y < 0:
			return
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.p[x] = y
				self.rank[y] += self.rank[x]
			else:
				self.p[y] = x
				self.rank[x] += self.rank[y]

def add(d, key, val):
	if key not in d:
		d[key] = 0
	d[key] += val
	if d[key] == 0:
		del d[key]

def update(i, used, d, u):
	used[i] = True
	add(d, 1, 1)
	if i - 1 >= 0 and used[i - 1] == True:
		par_1 = u.find(i)
		par_2 = u.find(i - 1)
		size_1 = u.rank[par_1]
		size_2 = u.rank[par_2]
		add(d, size_1, -1)
		add(d, size_2, -1)
		add(d, size_1 + size_2, 1)
		u.union(par_1, par_2)
	if i + 1 < n and used[i + 1] == True:
		par_1 = u.find(i)
		par_2 = u.find(i + 1)
		size_1 = u.rank[par_1]
		size_2 = u.rank[par_2]
		add(d, size_1, -1)
		add(d, size_2, -1)
		add(d, size_1 + size_2, 1)
		u.union(par_1, par_2)
n = int(input())
a_ = list(map(int, input().split()))
a = [(i, x) for (i, x) in enumerate(a_)]
a = sorted(a, key=lambda x: x[1])
u = Union(n)
d = {}
used = [False] * n
ans = -1
max_length = -1
for (index, val) in a:
	update(index, used, d, u)
	if len(d) == 1:
		len_ = list(d.values())[0]
		if max_length < len_:
			max_length = len_
			ans = val + 1
print(ans)


def main():
	n = int(input())
	ori_a = [int(x) for x in input().split()]
	pos = {ori_a[i]: i for i in range(len(ori_a))}
	seg = [dict(left=None, right=None) for i in range(len(ori_a))]
	a = sorted(ori_a)
	seg_size = 0
	seg_num = 0
	fi_k = a[0]
	fi_seg_num = 0
	for (n_items, item) in enumerate(a, 1):
		i = pos[item]
		(seg[i]['left'], seg[i]['right']) = (i, i)
		seg_num += 1
		size = seg[i]['right'] - seg[i]['left'] + 1
		if size > seg_size:
			seg_size = size
		li = pos[item] - 1
		if 0 <= li:
			if seg[li]['right'] == i - 1:
				seg[i]['left'] = seg[li]['left']
				seg[li]['right'] = seg[i]['left']
				seg_num -= 1
				size = seg[i]['right'] - seg[i]['left'] + 1
				if size > seg_size:
					seg_size = size
		ri = pos[item] + 1
		if ri < n:
			if seg[ri]['left'] == i + 1:
				seg[i]['right'] = seg[ri]['right']
				seg[ri]['left'] = seg[i]['left']
				seg_num -= 1
				size = seg[i]['right'] - seg[i]['left'] + 1
				if size > seg_size:
					seg_size = size
		if seg_size * seg_num == n_items and seg_num > fi_seg_num:
			fi_seg_num = seg_num
			fi_k = item + 1
	print(fi_k)
main()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
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')

def find(u):
	if parent[u] == -1:
		return -1
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def union(a, b):
	u = parent[a]
	v = parent[b]
	if size[u] > size[v]:
		parent[v] = u
		size[u] += size[v]
	else:
		parent[u] = v
		size[v] += size[u]
n = int(input())
parent = [-1 for i in range(n + 2)]
size = [1 for i in range(n + 2)]
b = list(map(int, input().split()))
c = []
for i in range(n):
	c.append([b[i], i + 1])
c.sort()
ans = 0
le = 0
d = defaultdict(lambda : 0)
cnt = 0
for j in range(n):
	(val, ind) = c[j]
	lpar = find(ind - 1)
	rpar = find(ind + 1)
	parent[ind] = ind
	if lpar != -1:
		sz1 = size[find(lpar)]
		d[sz1] += -1
		if d[sz1] == 0:
			cnt += -1
		union(ind - 1, ind)
	if rpar != -1:
		sz2 = size[find(rpar)]
		d[sz2] += -1
		if d[sz2] == 0:
			cnt += -1
		union(ind, ind + 1)
	sz = size[find(ind)]
	d[sz] += 1
	if d[sz] == 1:
		cnt += 1
	if cnt == 1:
		if d[sz] > le:
			le = d[sz]
			ans = val + 1
print(ans)


import bisect

def getIntList():
	return list(map(int, input().split()))

def getTransIntList(n):
	first = getIntList()
	m = len(first)
	result = [[0] * n for _ in range(m)]
	for i in range(m):
		result[i][0] = first[i]
	for j in range(1, n):
		curr = getIntList()
		for i in range(m):
			result[i][j] = curr[i]
	return result
n = int(input())
a = getIntList()
anums = [(a[i], i) for i in range(n)]
anums.sort()
location = 0
length = 0
k = 1
pieces = []

def upgrade(x):
	curr = (x, x + 1)
	i = bisect.bisect(pieces, curr)
	joinLeft = False
	joinRight = False
	if i > 0 and pieces[i - 1][1] == x:
		joinLeft = True
	if i < len(pieces) and pieces[i][0] == x + 1:
		joinRight = True
	if joinLeft:
		if joinRight:
			pieces[i - 1] = (pieces[i - 1][0], pieces[i][1])
			pieces.pop(i)
		else:
			pieces[i - 1] = (pieces[i - 1][0], x + 1)
		return pieces[i - 1][1] - pieces[i - 1][0]
	else:
		if joinRight:
			pieces[i] = (x, pieces[i][1])
		else:
			pieces.insert(i, curr)
		return pieces[i][1] - pieces[i][0]
currLength = 0
currSum = 0
for x in anums:
	currSum += 1
	(val, num) = x
	l = upgrade(num)
	currLength = max(currLength, l)
	if currLength * len(pieces) == currSum:
		currK = val + 1
		currLocation = len(pieces)
		if currLocation > location:
			location = currLocation
			k = currK
	if (location + 2) * currLength - 1 > n:
		break
print(k)