"We've tried solitary confinement, waterboarding and listening to Just In Beaver, to no avail. We need something extreme."

"Little Alena got an array as a birthday present..."

The array b of length n is obtained from the array a of length n and two integers l and r (l ≤ r) using the following procedure:

b_1 = b_2 = b_3 = b_4 = 0.

For all 5 ≤ i ≤ n:   b_{i} = 0 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 > r and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 1  b_{i} = 1 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 < l and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 0  b_{i} = b_{i} - 1 otherwise 

You are given arrays a and b' of the same length. Find two integers l and r (l ≤ r), such that applying the algorithm described above will yield an array b equal to b'.

It's guaranteed that the answer exists.


-----Input-----

The first line of input contains a single integer n (5 ≤ n ≤ 10^5) — the length of a and b'.

The second line of input contains n space separated integers a_1, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the elements of a.

The third line of input contains a string of n characters, consisting of 0 and 1 — the elements of b'. Note that they are not separated by spaces.


-----Output-----

Output two integers l and r ( - 10^9 ≤ l ≤ r ≤ 10^9), conforming to the requirements described above.

If there are multiple solutions, output any of them.

It's guaranteed that the answer exists.


-----Examples-----
Input
5
1 2 3 4 5
00001

Output
6 15

Input
10
-10 -9 -8 -7 -6 6 7 8 9 10
0000111110

Output
-5 5



-----Note-----

In the first test case any pair of l and r pair is valid, if 6 ≤ l ≤ r ≤ 10^9, in that case b_5 = 1, because a_1, ..., a_5 < l.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation


Solutions:
def main():
	(n, aa, s) = (int(input()), list(map(float, input().split())), input())
	(l, r, abuf, bbuf) = (-1000000001.0, 1000000001.0, aa[:5], [False] * 4)
	for i in range(4, n):
		(abuf[i % 5], b) = (aa[i], s[i] == '1')
		if b:
			if not any(bbuf) and l < max(abuf):
				l = max(abuf)
		elif all(bbuf) and r > min(abuf):
			r = min(abuf)
		bbuf[i % 4] = b
	print(int(l) + 1, int(r) - 1)
main()


(n, a, b, l, r) = (int(input()), list(map(int, input().split())), input(), -10 ** 9, 10 ** 9)
for i in range(4, n):
	if b[i - 4:i + 1] == '00001':
		l = max(l, max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1)
	if b[i - 4:i + 1] == '11110':
		r = min(r, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1)
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
l = -10 ** 9
r = 10 ** 9
for i in range(4, n):
	if b[i] == '1' and b[i - 4:i] == '0000':
		l = max(l, max([a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]]) + 1)
	elif b[i] == '0' and b[i - 4:i] == '1111':
		r = min(r, min([a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]]) - 1)
print(l, r)


n = int(input())
a = list(map(int, input().split()))
s = list(input())
l = -1000000000
r = 1000000000
for i in range(4, len(s)):
	if s[i] == '1' and s[i - 1] == '0':
		l = max(l, max(a[i - 1], a[i - 2], a[i - 3], a[i - 4], a[i]) + 1)
	elif s[i] == '0' and s[i - 1] == '1':
		r = min(r, min(a[i - 1], a[i - 2], a[i - 3], a[i - 4], a[i]) - 1)
print(l, r)


n = int(input())
arr = list(map(int, input().split()))
s = input()
ptr = 4
l = -10 ** 9
r = 10 ** 9
while ptr < n:
	if s[ptr - 4:ptr + 1] == '00001':
		l = max(max(arr[ptr - 4:ptr + 1]) + 1, l)
	elif s[ptr - 4:ptr + 1] == '11110':
		r = min(min(arr[ptr - 4:ptr + 1]) - 1, r)
	ptr += 1
print(l, r)


from sys import stdin as cin

def main():
	n = int(input())
	a = list(map(int, input().split()))
	b = input()
	(l, r) = ('?', '?')
	for i in range(1, n):
		if b[i] == '1' and b[i - 1] == '0':
			if l == '?':
				l = 1 + max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4])
			else:
				l = max(l, 1 + max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]))
		if b[i] == '0' and b[i - 1] == '1':
			if r == '?':
				r = min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1
			else:
				r = min(r, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1)
	if l == '?':
		l = -1000000000
	if r == '?':
		r = 1000000000
	print(l, r)
main()


n = int(input())
a = list(map(int, input().split()))
s = str(input())
lmin = rmin = -1000000000.0
lmax = rmax = 1000000000.0
for i in range(4, len(s)):
	if s[i] == '0' and s[i - 1] == '0' or (s[i] == '1' and s[i - 1] == '1'):
		lmax = min(lmax, max([a[i - j] for j in range(5)]))
		rmin = max(rmin, min([a[i - j] for j in range(5)]))
	elif s[i] == '1' and s[i - 1] == '0':
		lmin = max(lmin, max([a[i - j] for j in range(5)]) + 1)
	else:
		rmax = min(rmax, min([a[i - j] for j in range(5)]) - 1)
print(int(lmin), int(rmax))


n = int(input())
a = [*map(int, input().split())]
b = input()
(l, r) = (-10 ** 9, 10 ** 9)
for i in range(4, n):
	if b[i] == b[i - 1]:
		continue
	mx = max(a[i - 4:i + 1])
	mn = min(a[i - 4:i + 1])
	if b[i] == '0':
		r = min(r, mn - 1)
	else:
		l = max(l, mx + 1)
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
r = 1000000000.0
l = -1000000000.0
for i in range(4, n):
	if b[i - 4:i] == '1111' and b[i] == '0':
		r = min(r, min(a[i - 4:i + 1]) - 1)
	if b[i - 4:i] == '0000' and b[i] == '1':
		l = max(l, max(a[i - 4:i + 1]) + 1)
print(int(l), int(r))


import time
import math
debug = False
nDayQuant = int(input())
Temps = list(map(int, input().split(' ')))
Status = input()
nMaxTemp = 1000000000
nMinTemp = -1000000000
nLowTempMin = nMinTemp
nLowTempMax = nMaxTemp
nHighTempMin = nMinTemp
nHighTempMax = nMaxTemp
if debug:
	print('---')
begin = time.time()

def max5(nDay):
	global Temps
	nRet = Temps[nDay]
	for i in range(nDay - 4, nDay):
		if Temps[i] > nRet:
			nRet = Temps[i]
	return nRet

def min5(nDay):
	global Temps
	nRet = Temps[nDay]
	for i in range(nDay - 4, nDay):
		if Temps[i] < nRet:
			nRet = Temps[i]
	return nRet
nLastStatus = '0'
nOffCount = 4
nOnCount = 0
for i in range(4, nDayQuant):
	if debug:
		print('i: ', i)
	if Status[i] == '1':
		nOnCount += 1
		nOffCount = 0
	else:
		nOnCount = 0
		nOffCount += 1
	if Status[i] != nLastStatus:
		if debug:
			print('Status[i]: ', Status[i])
		if Status[i] == '1':
			nCurrTemp = max5(i)
			if debug:
				print('nCurrTemp: ', nCurrTemp)
			if nCurrTemp >= nLowTempMin:
				nLowTempMin = nCurrTemp + 1
				if debug:
					print('(Change) nLowTempMin: ', nLowTempMin)
		else:
			nCurrTemp = min5(i)
			if debug:
				print('nCurrTemp: ', nCurrTemp)
			if nCurrTemp <= nHighTempMax:
				nHighTempMax = nCurrTemp - 1
				if debug:
					print('(Change) nHighTempMax: ', nHighTempMax)
		nLastStatus = Status[i]
	else:
		if nOnCount > 4:
			nCurrTemp = min5(i)
			if debug:
				print('nCurrTemp: ', nCurrTemp)
			if nCurrTemp > nHighTempMin:
				nHighTempMin = nCurrTemp
				if debug:
					print('(Save) nHighTempMin: ', nHighTempMin)
		if nOffCount > 4:
			nCurrTemp = max5(i)
			if debug:
				print('nCurrTemp: ', nCurrTemp)
			if nCurrTemp < nLowTempMax:
				nLowTempMax = nCurrTemp
				if debug:
					print('(Save) nLowTempMax: ', nLowTempMax)
if debug:
	print(nLowTempMin, nLowTempMax, nHighTempMin, nHighTempMax)
if nHighTempMin < nLowTempMin:
	nHighTempMin = nLowTempMin
if nLowTempMax > nHighTempMax:
	nLowTempMax = nHighTempMax
if debug:
	print(nLowTempMin, nLowTempMax, nHighTempMin, nHighTempMax)
if nLowTempMax <= nHighTempMin:
	print(nLowTempMax, nHighTempMin)
elif nHighTempMin != nMinTemp:
	print(nHighTempMin, nHighTempMin)
else:
	print(nLowTempMax, nLowTempMax)
if debug:
	print(time.time() - begin)
if debug:
	print('---')


n = int(input())
arr = list(map(int, input().split()))
brr = input()
l = -10 ** 9
r = 10 ** 9
for i in range(4, n):
	if brr[i - 1] == brr[i - 2] == brr[i - 3] == brr[i - 4] != brr[i]:
		if brr[i] == '1':
			l = max(l - 1, arr[i], arr[i - 1], arr[i - 2], arr[i - 3], arr[i - 4]) + 1
		else:
			r = min(r + 1, arr[i], arr[i - 1], arr[i - 2], arr[i - 3], arr[i - 4]) - 1
print(l, r)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, list(input())))
	LMIN = -10 ** 9
	LMAX = 10 ** 9
	RMIN = -10 ** 9
	RMAX = 10 ** 9
	for i in range(4, n):
		if b[i - 1] == 0 and b[i - 2] == 0 and (b[i - 3] == 0) and (b[i - 4] == 0):
			if b[i] == 1:
				LMIN = max(LMIN, max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1)
			elif b[i] == 0:
				LMAX = min(LMAX, max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]))
		elif b[i - 1] == 1 and b[i - 2] == 1 and (b[i - 3] == 1) and (b[i - 4] == 1):
			if b[i] == 1:
				RMIN = max(RMIN, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]))
			elif b[i] == 0:
				RMAX = min(RMAX, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1)
		else:
			pass
	print(LMIN, RMAX)
solve()


inf = int(1000000000.0)
M = mod = 1000000007
mod2inv = 500000004
pt = lambda *a, **k: print(*a, **k, flush=True)
rd = lambda : map(int, input().split())
n = int(input())
a = list(rd())
b = input()
l1 = -inf
l2 = inf
r1 = -inf
r2 = inf
f = 4
for i in range(4, n):
	x = b[i]
	if f == 4 and x == '1':
		l1 = max(l1, max(a[i - 4:i + 1]) + 1)
		f = 0
	if f == 4 and x == '0':
		l2 = min(l2, max(a[i - 4:i + 1]))
	if f == -4 and x == '1':
		r1 = max(r1, min(a[i - 4:i + 1]))
	if f == -4 and x == '0':
		r2 = min(r2, min(a[i - 4:i + 1]) - 1)
		f = 0
	if -4 < f < 4:
		if x == '0':
			f += 1
		if x == '1':
			f -= 1
print(min(l1, l2), max(r1, r2))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, list(input())))
current = 0
l = 10 ** 9 * -1
r = 10 ** 9
for i in range(n):
	if b[i] != current:
		current = b[i]
		if b[i] == 0:
			r = min(r, min(a[i - 4:i + 1]) - 1)
		else:
			l = max(l, max(a[i - 4:i + 1]) + 1)
print(l, r, end=' ')


n = int(input())
arr = list(map(int, input().split()))
s = list(map(int, input()))
t1 = [0, 0, 0, 0, 1]
t2 = [1, 1, 1, 1, 0]
window = []
(l, r) = (-10 ** 9, 10 ** 9)
for i in range(4):
	window.append(s[i])
cnt = 0
for i in range(4, n):
	window.append(s[i])
	if window == t1:
		x = max(arr[cnt:cnt + 5])
		l = max(l, x + 1)
	elif window == t2:
		x = min(arr[cnt:cnt + 5])
		r = min(r, x - 1)
	window.pop(0)
	cnt += 1
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = list(map(lambda x: 1 if x == '1' else 0, input()))
(left, right) = (-10 ** 9, 10 ** 9)
for i in range(4, n):
	test = True
	for j in range(2, 5):
		if b[i - j] != b[i - 1]:
			test = False
	if not test:
		continue
	if b[i] == 0 and b[i - 1] == 1:
		for j in range(5):
			right = min(right, a[i - j] - 1)
	if b[i] == 1 and b[i - 1] == 0:
		for j in range(5):
			left = max(left, a[i - j] + 1)
print(left, right)


n = int(input())
a = list(map(int, input().split()))
b = input()
(l, r) = (-10 ** 9, 10 ** 9)
for (i, el) in enumerate(b[4:], 4):
	if b[i - 4:i] == '0000' and el == '1':
		l = max(l, max(a[i - 4:i + 1]) + 1)
	elif b[i - 4:i] == '1111' and el == '0':
		r = min(r, min(a[i - 4:i + 1]) - 1)
print(l, r)


l = [-int(1000000000.0), int(1000000000.0)]
r = [-int(1000000000.0), int(1000000000.0)]
n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input()]
sumb = sum(b[:3])
for i in range(4, n):
	maxa = max(a[i - 4:i + 1])
	mina = min(a[i - 4:i + 1])
	sumb = sumb + b[i - 1] - (b[i - 5] if i - 5 >= 0 else 0)
	if b[i] == 1:
		if sumb == 4:
			r[0] = max(r[0], mina)
		elif b[i - 1] == 0 and sumb == 0:
			l[0] = max(l[0], maxa + 1)
	elif sumb == 0:
		l[1] = min(l[1], maxa)
	elif b[i - 1] == 1 and sumb == 4:
		r[1] = min(r[1], mina - 1)
print('%d %d' % (l[0], r[1]))

def verify(a, b):
	for i in range(4, n):
		t = b[i - 1]
		if min(a[i - 4:i + 1]) > r[1] and sum(b[i - 4:i]) == 4:
			t = 0
		elif max(a[i - 4:i + 1]) < l[0] and sum(b[i - 4:i]) == 0:
			t = 1
		assert t == b[i]


n = int(input())
a = [int(x) for x in input().split(' ')]
b = input()
llow = -1000000000
lhigh = 1000000000
rlow = -1000000000
rhigh = 1000000000
i = 4
last = 0
while i < n:
	if int(b[i]) == last:
		if last == 1:
			if min(a[i - 4:i + 1]) > rlow:
				rlow = min(a[i - 4:i + 1])
		elif max(a[i - 4:i + 1]) < llow:
			lhigh = max(a[i - 4:i + 1])
		i += 1
	else:
		if last == 1:
			if min(a[i - 4:i + 1]) <= rhigh:
				rhigh = min(a[i - 4:i + 1]) - 1
		elif max(a[i - 4:i + 1]) >= llow:
			llow = max(a[i - 4:i + 1]) + 1
		last = 1 - last
		i += 4
	if llow == lhigh and rlow == rhigh:
		break
print(str(llow) + ' ' + str(rhigh))


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input()]
z = [0] * 4
o = [1] * 4
k = 1000000000
lmin = -k
rmax = k
rmin = -k
lmax = k
for i in range(4, n):
	a1 = min(a[i - 4:i + 1])
	a2 = max(a[i - 4:i + 1])
	b1 = b[i - 4:i] == o
	b2 = b[i - 4:i] == z
	if b1 and b[i] == 0:
		rmax = min(rmax, a1 - 1)
	elif b2 and b[i] == 1:
		lmin = max(lmin, a2 + 1)
print(lmin, rmax)


def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = input()
	re = int(1000000000.0)
	le = -re
	x = True
	for i in range(n):
		if b[i] == ('1' if x else '0'):
			for j in a[i - 4:i + 1]:
				if x:
					if le <= j:
						le = j + 1
				elif re >= j:
					re = j - 1
			x = not x
	print(le, re)

def __starting_point():
	main()
__starting_point()


import sys
n = int(input())
A = input().split()
A = [int(i) for i in A]
S = input()
L = -1000000000
R = 1000000000
for i in range(4, n):
	if S[i - 1] == S[i - 2] == S[i - 3] == S[i - 4] == '0' and S[i] == '1':
		L = max(max(A[i], A[i - 1], A[i - 2], A[i - 3], A[i - 4]) + 1, L)
	elif S[i - 1] == S[i - 2] == S[i - 3] == S[i - 4] == '1' and S[i] == '0':
		R = min(min(A[i], A[i - 1], A[i - 2], A[i - 3], A[i - 4]) - 1, R)
	elif S[i - 1] == S[i - 2] == S[i - 3] == S[i - 4] == '0' and S[i] == '0':
		L = min(max(A[i], A[i - 1], A[i - 2], A[i - 3], A[i - 4]), L)
	elif S[i - 1] == S[i - 2] == S[i - 3] == S[i - 4] == '1' and S[i] == '1':
		R = max(min(A[i], A[i - 1], A[i - 2], A[i - 3], A[i - 4]), R)
print('{} {}'.format(L, R))


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(input().rstrip())
for i in range(n):
	b[i] = int(b[i])
(l, r) = (-10 ** 9, 10 ** 9)
for i in range(4, n):
	if b[i] == b[i - 1]:
		if not b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4]:
			continue
		if b[i] == 0:
			if max(a[i - 4:i + 1]) < l:
				l = max(a[i - 4:i + 1]) - 1
		elif min(a[i - 4:i + 1]) > r:
			r = min(a[i - 4:i + 1]) + 1
	elif b[i] == 1:
		if max(a[i - 4:i + 1]) >= l:
			l = max(a[i - 4:i + 1]) + 1
	elif min(a[i - 4:i + 1]) <= r:
		r = min(a[i - 4:i + 1]) - 1
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
r = 1000000000
l = -r
for i in range(4, n):
	if b[i - 1] != b[i]:
		if b[i] == '0':
			r = min(r, min(a[i - 4:i + 1]) - 1)
		else:
			l = max(l, max(a[i - 4:i + 1]) + 1)
print(l, r)


def check(lst, val):
	return lst[1:] == lst[:-1] and lst[0] == val
n = int(input())
a = [int(s) for s in input().split(' ')]
b_ = [int(s) for s in list(input())]
l = -10 ** 9
r = 10 ** 9
list_ = b_[:4]
for i in range(4, len(b_)):
	if check(list_, 0):
		if b_[i] == 1:
			l = max(max(a[i - 4:i + 1]) + 1, l)
	elif check(list_, 1):
		if b_[i] == 0:
			r = min(r, min(a[i - 4:i + 1]) - 1)
	list_.pop(0)
	list_.insert(len(list_), b_[i])
print(str(l) + ' ' + str(r))


n = int(input())
ls = list(map(int, input().split()))
s = input()
r = int(1000000000.0)
l = -r
i = 4
while i < n:
	if s[i] == s[i - 1]:
		i += 1
		continue
	if s[i] == '1':
		l = max(l, max(ls[i - 4:i + 1]) + 1)
	elif s[i] == '0':
		r = min(r, min(ls[i - 4:i + 1]) - 1)
	i += 1
print(l, r)


n = int(input())
arr = [int(z) for z in input().split()]
b = [int(z) for z in input()]
(l, r) = (-10 ** 9, 10 ** 9)
for i in range(1, n):
	if b[i] != b[i - 1]:
		if b[i] == 1:
			for k in range(5):
				l = max(l - 1, arr[i - k]) + 1
		if b[i] == 0:
			for k in range(5):
				r = min(r + 1, arr[i - k]) - 1
print(l, r)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
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())
a = list(map(int, input().split()))
s = input()
r = 10 ** 9
l = -10 ** 9
for i in range(4, n):
	if s[i - 1] == s[i - 2] == s[i - 3] == s[i - 4] == '1' and s[i] == '0':
		r1 = min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1
		r = min(r, r1)
	elif s[i - 1] == s[i - 2] == s[i - 3] == s[i - 4] == '0' and s[i] == '1':
		l1 = max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1
		l = max(l, l1)
print(l, r)


class SegTree:

	def __init__(self, init_val, ide_ele, segfunc):
		self.n = len(init_val)
		self.num = 2 ** (self.n - 1).bit_length()
		self.ide_ele = ide_ele
		self.segfunc = segfunc
		self.seg = [ide_ele] * 2 * self.num
		for i in range(self.n):
			self.seg[i + self.num] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.seg[k] = x
		while k:
			k = k >> 1
			self.seg[k] = self.segfunc(self.seg[2 * k], self.seg[2 * k + 1])

	def query(self, l, r):
		if r <= l:
			return self.ide_ele
		l += self.num
		r += self.num
		lres = self.ide_ele
		rres = self.ide_ele
		while l < r:
			if r & 1:
				r -= 1
				rres = self.segfunc(self.seg[r], rres)
			if l & 1:
				lres = self.segfunc(lres, self.seg[l])
				l += 1
			l = l >> 1
			r = r >> 1
		res = self.segfunc(lres, rres)
		return res
INF = 10 ** 18

def main():
	n = int(input())
	A = list(map(int, input().split()))
	B = str(input())
	ms = SegTree(A, INF, min)
	Ms = SegTree(A, -INF, max)
	r = INF
	l = -INF
	for i in range(4, n):
		if B[i] == '0' and B[i - 1] == '1' and (B[i - 2] == '1') and (B[i - 3] == '1') and (B[i - 4] == '1'):
			r = min(r, ms.query(i - 4, i + 1) - 1)
		if B[i] == '1' and B[i - 1] == '0' and (B[i - 2] == '0') and (B[i - 3] == '0') and (B[i - 4] == '0'):
			l = max(l, Ms.query(i - 4, i + 1) + 1)
	if r > 10 ** 9:
		r = 10 ** 9
	if l < -10 ** 9:
		l = -10 ** 9
	print(l, r)
main()


3
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input()))
l = None
r = None
i = 4
while i < n:
	if b[i] == 0 and b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == 1:
		if r is None:
			r = min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1
		else:
			r = min(r, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1)
	elif b[i] == 1 and b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == 0:
		if l is None:
			l = max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1
		else:
			l = max(l, max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1)
	i += 1
if l is None:
	l = -1000000000
if r is None:
	r = 1000000000
print('%s %s' % (l, r))


(n, a, s) = (int(input()), list(map(int, input().split())), input())
(l, r) = (-1000000001, 1000000001)
for i in range(4, n):
	if s[i] == '1' and s[i - 4:i] == '0000':
		l = max(l, max(a[i - 4:i + 1]))
	elif s[i] == '0' and s[i - 4:i] == '1111':
		r = min(r, min(a[i - 4:i + 1]))
print(l + 1, r - 1)


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input()]
z = [0] * 4
o = [1] * 4
k = 1000000000
l = -k
r = k
for i in range(4, n):
	a1 = a[i - 4:i + 1]
	b1 = b[i - 4:i]
	if b1 == o and b[i] == 0:
		t = min(a1)
		r = min(r, t - 1)
	elif b1 == z and b[i] == 1:
		t = max(a1)
		l = max(l, t + 1)
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
change = []
for i in range(1, n):
	if b[i - 1] != b[i]:
		change.append(i)
maxl = max(a) + 5
minl = min(a) - 5
minr = min(a) - 5
maxr = max(a) + 5
x = len(change)
for i in range(x - 1, -1, -1):
	j = change[i]
	if b[j] == '1':
		minl = max(minl, max(a[j - 4:j + 1]))
	else:
		maxr = min(maxr, min(a[j - 4:j + 1]))
	j -= 4
	while change[i - 1] < j:
		j -= 1
		if a[j] > minl:
			maxl = min(maxl, a[j])
		else:
			minr = max(minr, a[j])
l = minl + 1
r = maxr - 1
print(l, r)


import os
import sys
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

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

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(1):
	n = Int()
	a = array()
	b = [int(i) for i in input()]
	l = -10 ** 9
	r = 10 ** 9
	for i in range(1, n):
		if b[i] == b[i - 1]:
			continue
		elif b[i] == 1:
			for j in range(5):
				l = max(a[i - j] + 1, l)
		else:
			for j in range(5):
				r = min(a[i - j] - 1, r)
	print(l, r)


from sys import stdin, stdout
from random import randrange
n = int(stdin.readline())
values = list(map(int, stdin.readline().split()))
b = list(stdin.readline().strip())
(mx, mn) = (values[:], values[:])
for i in range(4, n):
	for j in range(i - 4, i + 1):
		mx[i] = max(mx[i], values[j])
		mn[i] = min(mn[i], values[j])
INF = 10 ** 9
(l, r) = (INF, -INF)
for i in range(4, n):
	if b[i] == b[i - 1]:
		if b[i - 4] == b[i - 3] == b[i - 2] == b[i - 1] == '1' and mn[i] > r:
			r = mn[i]
		elif b[i - 4] == b[i - 3] == b[i - 2] == b[i - 1] == '0' and mx[i] < l:
			l = mx[i]
(lb, rb) = (l, r)
(l, r) = (-INF, INF)
for i in range(4, n):
	if b[i] == b[i - 1]:
		continue
	if b[i] == '0':
		r = min(mn[i] - 1, r)
	else:
		l = max(mx[i] + 1, l)
stdout.write(str(l) + ' ' + str(r) + '\n')


n = int(input())
a = list(map(int, input().split()))
b = list(input())
b = list(map(int, b))
inf = int(1000000000.0)
l = [-inf, inf]
r = [-inf, inf]
for i in range(4, n):
	Max = max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4])
	Min = min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4])
	if b[i] == 0:
		if b[i - 1] and b[i - 2] and b[i - 3] and b[i - 4]:
			r[1] = min(r[1], Min - 1)
		elif not (b[i - 1] or b[i - 2] or b[i - 3] or b[i - 4]):
			l[1] = max(l[1], Max)
	elif b[i - 1] and b[i - 2] and b[i - 3] and b[i - 4]:
		r[0] = max(r[0], Min)
	elif not (b[i - 1] or b[i - 2] or b[i - 3] or b[i - 4]):
		l[0] = max(l[0], Max + 1)
print(l[0], r[1])


n = int(input())
a = input().split()
a = [int(k) for k in a]
b = input()
l = -1000000000
r = 1000000000
for i in range(4, len(b)):
	if b[i - 1] == '0' and b[i] == '1':
		l = max([l, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]])
	if b[i] == '0' and b[i - 1] == '1':
		r = min([r, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]])
print(l + 1, r - 1)


_ = input()
numbers = [int(x) for x in input().split()]
bits = input()
INF = int(1000000000.0)
lowerBoundL = -INF
upperBoundL = INF
lowerBoundR = -INF
upperBoundR = INF
for pos in range(4, len(bits)):
	window = slice(pos - 4, pos + 1)
	if bits[window] == '00000':
		upperBoundL = min(upperBoundL, *numbers[window])
	elif bits[window] == '00001':
		lowerBoundL = max(lowerBoundL, *(x + 1 for x in numbers[window]))
	elif bits[window] == '11111':
		lowerBoundR = max(lowerBoundR, *numbers[window])
	elif bits[window] == '11110':
		upperBoundR = min(upperBoundR, *(x - 1 for x in numbers[window]))
print(lowerBoundL, upperBoundR)


n = int(input())
arr = []
inf = 2000000000

def mini(idx):
	return min(arr[idx], min(arr[idx - 1], min(arr[idx - 2], min(arr[idx - 3], arr[idx - 4]))))

def maxi(idx):
	return max(arr[idx], max(arr[idx - 1], max(arr[idx - 2], max(arr[idx - 3], arr[idx - 4]))))
arr = [int(x) for x in input().split()]
str = input()
zero = 4
one = 0
l = -inf
r = inf
for i in range(4, n):
	if zero == 4 and str[i] == '1':
		l = max(l, maxi(i))
	if one == 4 and str[i] == '0':
		r = min(r, mini(i))
	if str[i - 4] == '1':
		one = one - 1
	else:
		zero = zero - 1
	if str[i] == '0':
		zero = zero + 1
	else:
		one = one + 1
if l != -inf:
	l = l + 1
if r != inf:
	r = r - 1
elif l != -inf and r == inf:
	r = l
	for i in range(4, n):
		r = max(r, mini(i))
elif l == -inf and r == inf:
	l = inf
	for i in range(4, n):
		l = min(l, maxi(i))
	r = l
print(l, r)


n = int(input())
a = input().split()
b = input()
_b = list()
for i in range(len(a)):
	a[i] = int(a[i])
for l in b:
	_b.append(int(l))
b = _b
r = 10 ** 9
l = -10 ** 9
for i in range(len(b)):
	if i > 3:
		if b[i] == 0 and b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == 1:
			if min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1 < r:
				r = min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1
		elif b[i] == 1 and b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == 0:
			if max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1 > l:
				l = max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1
print(l, r)


import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input()))
l = -10 ** 9
r = 10 ** 9
p = a[0:5]
for i in range(4, n):
	if b[i] == 1 and sum(b[i - 4:i]) == 0:
		l = max(l, max(a[i - 4:i + 1]))
	elif b[i] == 0 and sum(b[i - 4:i]) == 4:
		r = min(r, min(a[i - 4:i + 1]))
print(l + 1, r - 1)


import re
input()
a = list(map(int, input().split()))
b = input()
(l, r) = (-10 ** 9, 10 ** 9)
for m in re.finditer('11110', b):
	i = m.start(0)
	r = min([r + 1] + a[i:i + 5]) - 1
for m in re.finditer('00001', b):
	i = m.start(0)
	l = max([l - 1] + a[i:i + 5]) + 1
print(l, r)


def run():
	n = int(input())
	a = [int(x) for x in input().split()]
	bt = [int(x) for x in input()]
	lmin = -10 ** 9
	lmax = -lmin
	rmin = lmin
	rmax = lmax
	for i in range(4, n):
		prev = bt[i - 1] + bt[i - 2] + bt[i - 3] + bt[i - 4]
		if 0 < prev < 4:
			continue
		if prev == 0:
			acmp = max((a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]))
			if bt[i] == 1:
				lminc = acmp + 1
				lmin = lminc if lminc > lmin else lmin
			else:
				lmaxc = acmp
				lmax = lmaxc if lmaxc < lmax else lmax
		elif prev == 4:
			acmp = min((a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]))
			if bt[i] == 0:
				rmaxc = acmp - 1
				rmax = rmaxc if rmaxc < rmax else rmax
			else:
				rminc = acmp
				rmin = rminc if rminc > rmin else rmin
	print(f'{lmin} {rmax}')
run()


n = int(input())
a = list(map(int, input().split()))
b = input()
minl = int(-1000000000.0)
maxr = int(1000000000.0)
for i in range(4, n):
	if not b[i - 4] == b[i - 3] == b[i - 2] == b[i - 1] != b[i]:
		continue
	if b[i] == '0':
		maxr = min(maxr + 1, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1
	if b[i] == '1':
		minl = max(minl - 1, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1
print(minl, maxr)


from collections import deque

class FindExtremeKWindow:

	def update(self, el):
		raise NotImplemetedError('Not extended')

class FindExtremeMinKWindow(FindExtremeKWindow):

	def __init__(self):
		self.stack = deque()

	def remove(self, el):
		if len(self.stack) and self.stack[0] == el:
			self.stack.popleft()

	def update(self, el):
		while len(self.stack) and self.stack[-1] > el:
			self.stack.pop()
		self.stack.append(el)
		return self.stack[0]

	def get_first(self):
		return self.stack[0]

	def reset(self):
		self.stack = deque()

class FindExtremeMaxKWindow(FindExtremeKWindow):

	def __init__(self):
		self.stack = deque()

	def remove(self, el):
		if len(self.stack) and self.stack[0] == el:
			self.stack.popleft()

	def update(self, el):
		while len(self.stack) and self.stack[-1] < el:
			self.stack.pop()
		self.stack.append(el)
		return self.stack[0]

	def get_first(self):
		return self.stack[0]

	def reset(self):
		self.stack = deque()
n = int(input())
arr = list(map(int, input().split()))
b_arr = input()
min_window = FindExtremeMinKWindow()
max_window = FindExtremeMaxKWindow()
for i in range(4):
	max_window.update(arr[i])
i = 4
(l, r) = (-10 ** 9, 10 ** 9)
curr_window = max_window
other_window = min_window
while i < n:
	if b_arr[i] == b_arr[i - 1]:
		curr_window.remove(arr[i - 4])
		curr_window.update(arr[i])
	else:
		curr_window.update(arr[i])
		if b_arr[i] == '0':
			r_candidate = curr_window.get_first()
			r = min(r, r_candidate - 1)
		else:
			l_candidate = curr_window.get_first()
			l = max(l, l_candidate + 1)
		curr_window.reset()
		(other_window, curr_window) = (curr_window, other_window)
		curr_window.update(arr[i])
	i += 1
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
min_l = -1000000000
min_r = -1000000000
max_l = 1000000000
max_r = 1000000000
for i in range(4, n):
	if b[i] == '0':
		if b[i - 1] == '0':
			if b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == '0':
				max_l = min(max_l, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4])
		elif b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == '1':
			max_r = min(max_r, min(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) - 1)
		else:
			print('не может такого быть!')
	elif b[i - 1] == '1':
		if b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == '1':
			min_r = max(min_r, a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4])
	elif b[i - 1] == b[i - 2] == b[i - 3] == b[i - 4] == '0':
		min_l = max(min_l, max(a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]) + 1)
	else:
		print('не может такого быть!')
print(min_l, max_r)


n = int(input())
arr = list(map(int, input().split()))
b = list(map(int, list(input())))
l = int(-1000000000.0)
r = int(1000000000.0)
for i in range(4, n):
	if b[i] != b[i - 1]:
		if b[i]:
			m = -10000000000.0
			for g in range(i - 4, i + 1):
				m = max(arr[g], m)
			l = max(l, m + 1)
		else:
			m = 10000000000.0
			for g in range(i - 4, i + 1):
				m = min(arr[g], m)
			r = min(r, m - 1)
print(l, r)


(r, l) = ([[], []], [[], []])
n = int(input())
a = list(map(int, input().split()))
b = input()
s = '0'
t = 4
for (i, j) in enumerate(b[4:]):
	if j == s:
		if t >= 4:
			if j == '1':
				r[0].append(min(a[i], a[i + 1], a[i + 2], a[i + 3], a[i + 4]))
			else:
				l[0].append(max(a[i], a[i + 1], a[i + 2], a[i + 3], a[i + 4]))
		t += 1
	else:
		if j == '0':
			r[1].append(min(a[i], a[i + 1], a[i + 2], a[i + 3], a[i + 4]))
			s = '0'
		else:
			l[1].append(max(a[i], a[i + 1], a[i + 2], a[i + 3], a[i + 4]))
			s = '1'
		t = 1
if r[1] != []:
	r = min(r[1]) - 1
else:
	r = 10 ** 9
if l[1] != []:
	l = max(l[1]) + 1
else:
	l = -10 ** 9
print(' '.join((str(l), str(r))))


def findIntersection(intervals, N):
	if N == 0:
		return [-10 ** 9, -10 ** 9]
	l = intervals[0][0]
	r = intervals[0][1]
	for i in range(1, N):
		if intervals[i][0] > r or intervals[i][1] < l:
			print(-1)
		else:
			l = max(l, intervals[i][0])
			r = min(r, intervals[i][1])
	return [l, r]
n = int(int(input()))
a = list(map(int, input().split()))
r = input()
inter = []
for i in range(4, n):
	if int(r[i]) - int(r[i - 1]) == -1:
		inter.append([-10 ** 9, min(a[i - 1], a[i - 2], a[i - 3], a[i - 4], a[i]) - 1])
	elif int(r[i]) - int(r[i - 1]) == 1:
		inter.append([max(a[i - 1], a[i - 2], a[i - 3], a[i - 4], a[i]) + 1, 10 ** 9])
print(*findIntersection(inter, len(inter)))