CF940D.Alena And The Heater

"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.

我们尝试过单独监禁、水刑，甚至听《Just In Beaver》，但都无济于事。我们需要一些更极端的手段。

小阿莲生日时收到了一个数组……

长度为 $ n $ 的数组 $ b $ 是由长度为 $ n $ 的数组 $ a $ 及两个整数 $ l $ 和 $ r $（满足 $ l \leq r $）通过如下过程得到的：

$ b_1 = b_2 = b_3 = b_4 = 0 $。

对所有 $ 5 \leq i \leq n $：

• 若 $ a_i,, a_{i-1},, a_{i-2},, a_{i-3},, a_{i-4} > r $ 且 $ b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 1 $，则 $ b_i = 0 $；
• 若 $ a_i,, a_{i-1},, a_{i-2},, a_{i-3},, a_{i-4} < l $ 且 $ b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 0 $，则 $ b_i = 1 $；
• 否则 $ b_i = b_{i-1} $。

现给定两个等长的数组 $ a $ 和 $ b' $。请找出两个整数 $ l $ 和 $ r $（满足 $ l \leq r $），使得按上述算法处理数组 $ a $ 后所得的数组 $ b $ 恰好等于 $ b' $。

题目保证答案一定存在。

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

The second line of input contains n space separated integers _a_1, ..., a__n ( - 109 ≤ a__i ≤ 109) — 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.

输入的第一行包含一个整数 $n$（$5 \leq n \leq 10^5$）—— 表示数组 $a$ 和 $b$ 的长度。

输入的第二行包含 $n$ 个用空格分隔的整数 $a_1, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$）—— 表示数组 $a$ 的元素。

输入的第三行包含一个由 $n$ 个字符组成的字符串，每个字符为 0 或 1 —— 表示数组 $b$ 的元素。注意：这些字符之间不用空格分隔。

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

If there are multiple solutions, output any of them.

It's guaranteed that the answer exists.

输出两个整数 $l$ 和 $r$（满足 $-10^9 \le l \le r \le 10^9$），使其符合上述要求。

若存在多个解，输出其中任意一个即可。

保证答案一定存在。

In the first test case any pair of l and r pair is valid, if 6 ≤ l ≤ r ≤ 109, in that case _b_5 = 1, because _a_1, ..., _a_5 < l.

在第一个测试用例中，任意满足 $6 \leq l \leq r \leq 10^9$ 的 $l$ 和 $r$ 均为合法组合；此时 $b_5 = 1$，因为 $a_1, \ldots, a_5 < l$。