← 返回题目列表

Codeforces · 940/D

D. 阿莱娜和加热器

中文机器翻译题面 查看原题

“我们尝试过单独监禁、水刑和听Just In Beaver,但都没有效果。我们需要一些极端的东西。”

“小阿莱娜得到了一个数组作为生日礼物……”

长度为 n 的数组 b 是使用以下过程从长度为 n 的数组 a 和两个整数 l 和 r (l ≤ r) 获得的:

b1 = b2 = b3 = b4 = 0。

对于所有 5 ≤ i ≤ n:

- bi = 0 如果 ai, ai - 1, ai - 2, ai - 3, ai - 4 > r 且bi - 1 = bi - 2 = bi - 3 = bi - 4 = 1
- bi = 1,如果 ai, ai - 1, ai - 2, ai - 3, ai - 4 < l 且bi - 1 = bi - 2 = bi - 3 = bi - 4 = 0
- bi = bi - 1 否则

给定相同长度的数组 a 和 b'。找到两个整数 l 和 r (l ≤ r),这样应用上述算法将产生一个等于 b' 的数组 b。

保证答案存在。

输入

输入的第一行包含一个整数 n (5 ≤ n ≤ 105) — a 和 b' 的长度。

输入的第二行包含 n 个空格分隔的整数 a1, ..., an ( - 109 ≤ ai ≤ 109) - a 的元素。

输入的第三行包含 n 个字符的字符串,由 0 和 1 组成 - b' 的元素。请注意,它们之间没有用空格分隔。

输出

输出两个整数l和r (- 109 ≤ l ≤ r ≤ 109),符合上述要求。

如果有多个解,则输出其中任意一个。

保证答案存在。

示例

输入 #1

5
1 2 3 4 5
00001

输出 #1

6 15

输入 #2

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

输出 #2

-5 5

注意

在第一个测试用例中,任何一对 l 和 r 对都是有效的,如果 6 ≤ l ≤ r ≤ 109,在这种情况下 b5 = 1,因为 a1, ..., a5 < l。