{"raw_statement":[{"iden":"statement","content":"_\"We've tried solitary confinement, waterboarding and listening to Just In Beaver, to no avail. We need something extreme.\"_\n\n_\"Little Alena got an array as a birthday present...\"_\n\nThe 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:\n\n_b_1 = _b_2 = _b_3 = _b_4 = 0.\n\nFor all 5 ≤ _i_ ≤ _n_:\n\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\n*   _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\n*   _b__i_ = _b__i_ - 1 otherwise\n\nYou 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_'.\n\nIt's guaranteed that the answer exists."},{"iden":"input","content":"The first line of input contains a single integer _n_ (5 ≤ _n_ ≤ 105) — the length of _a_ and _b_'.\n\nThe second line of input contains _n_ space separated integers _a_1, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the elements of _a_.\n\nThe 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."},{"iden":"output","content":"Output two integers _l_ and _r_ ( - 109 ≤ _l_ ≤ _r_ ≤ 109), conforming to the requirements described above.\n\nIf there are multiple solutions, output any of them.\n\nIt's guaranteed that the answer exists."},{"iden":"examples","content":"Input\n\n5\n1 2 3 4 5\n00001\n\nOutput\n\n6 15\n\nInput\n\n10\n-10 -9 -8 -7 -6 6 7 8 9 10\n0000111110\n\nOutput\n\n\\-5 5"},{"iden":"note","content":"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_."}],"translated_statement":[{"iden":"statement","content":"\"我们尝试过单独监禁、水刑，甚至听《Just In Beaver》，但都无济于事。我们需要一些极端的手段。\"\n\n\"小阿莉娜收到了一个数组作为生日礼物#cf_span[...]\"\n\n长度为 #cf_span[n] 的数组 #cf_span[b] 是由长度为 #cf_span[n] 的数组 #cf_span[a] 和两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[l ≤ r]）通过以下过程得到的：\n\n#cf_span[b1 = b2 = b3 = b4 = 0]。\n\n对于所有 #cf_span[5 ≤ i ≤ n]：\n\n给定两个长度相同的数组 #cf_span[a] 和 #cf_span[b']。请找出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[l ≤ r]），使得应用上述算法后得到的数组 #cf_span[b] 与 #cf_span[b'] 相等。\n\n保证答案存在。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[5 ≤ n ≤ 105]）— 数组 #cf_span[a] 和 #cf_span[b'] 的长度。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）— 数组 #cf_span[a] 的元素。\n\n第三行包含一个由 #cf_span[n] 个字符组成的字符串，仅包含 _0_ 和 _1_ —— 数组 #cf_span[b'] 的元素。注意，它们之间没有空格。\n\n请输出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[ - 109 ≤ l ≤ r ≤ 109]），满足上述要求。\n\n如果有多个解，输出任意一个即可。\n\n保证答案存在。\n\n在第一个测试用例中，只要满足 #cf_span[6 ≤ l ≤ r ≤ 109]，任意一对 #cf_span[l] 和 #cf_span[r] 都是合法的，此时 #cf_span[b5 = 1]，因为 #cf_span[a1, ..., a5 < l]。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n]（#cf_span[5 ≤ n ≤ 105]）— 数组 #cf_span[a] 和 #cf_span[b'] 的长度。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）— 数组 #cf_span[a] 的元素。第三行包含一个由 #cf_span[n] 个字符组成的字符串，仅包含 _0_ 和 _1_ —— 数组 #cf_span[b'] 的元素。注意，它们之间没有空格。"},{"iden":"output","content":"请输出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[ - 109 ≤ l ≤ r ≤ 109]），满足上述要求。如果有多个解，输出任意一个即可。保证答案存在。"},{"iden":"examples","content":"输入：\n5\n1 2 3 4 5\n00001\n输出：\n6 15\n\n输入：\n10\n-10 -9 -8 -7 -6 6 7 8 9 10\n0000111110\n输出：\n-5 5"},{"iden":"note","content":"在第一个测试用例中，只要满足 #cf_span[6 ≤ l ≤ r ≤ 109]，任意一对 #cf_span[l] 和 #cf_span[r] 都是合法的，此时 #cf_span[b5 = 1]，因为 #cf_span[a1, ..., a5 < l]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 5 \\leq n \\leq 10^5 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers.  \nLet $ B' = (b'_1, b'_2, \\dots, b'_n) \\in \\{0,1\\}^n $ be a binary string interpreted as a sequence.  \n\nDefine a transformation parameterized by $ l, r \\in \\mathbb{Z} $ with $ l \\leq r $:  \nConstruct sequence $ B = (b_1, \\dots, b_n) $ as:  \n- $ b_1 = b_2 = b_3 = b_4 = 0 $,  \n- For $ 5 \\leq i \\leq n $:  \n  $$\n  b_i = \n  \\begin{cases} \n  1 & \\text{if } \\min(a_1, \\dots, a_{i-1}) \\geq l \\text{ and } \\max(a_1, \\dots, a_{i-1}) \\leq r \\\\\n  0 & \\text{otherwise}\n  \\end{cases}\n  $$\n\n**Constraints**  \n1. $ 5 \\leq n \\leq 10^5 $  \n2. $ -10^9 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ b'_i \\in \\{0,1\\} $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ b'_1 = b'_2 = b'_3 = b'_4 = 0 $ (implicit from problem)  \n\n**Objective**  \nFind integers $ l, r \\in \\mathbb{Z} $ such that $ l \\leq r $ and $ B = B' $, i.e.,  \n$$\n\\forall i \\in \\{5, \\dots, n\\}, \\quad b'_i = \\mathbb{I}\\left[ \\min_{1 \\leq j < i} a_j \\geq l \\text{ and } \\max_{1 \\leq j < i} a_j \\leq r \\right]\n$$  \nwhere $ \\mathbb{I}[\\cdot] $ is the indicator function.  \n\nOutput any such pair $ (l, r) $.","simple_statement":null,"has_page_source":false}