English · Original
Chinese · Translation
Formal · Original
_"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_ ≤ 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.
## Output
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.
[samples]
## Note
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_.
"我们尝试过单独监禁、水刑，甚至听《Just In Beaver》，但都无济于事。我们需要一些极端的手段。"
"小阿莉娜收到了一个数组作为生日礼物#cf_span[...]"
长度为 #cf_span[n] 的数组 #cf_span[b] 是由长度为 #cf_span[n] 的数组 #cf_span[a] 和两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[l ≤ r]）通过以下过程得到的：
#cf_span[b1 = b2 = b3 = b4 = 0]。
对于所有 #cf_span[5 ≤ i ≤ n]：
给定两个长度相同的数组 #cf_span[a] 和 #cf_span[b']。请找出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[l ≤ r]），使得应用上述算法后得到的数组 #cf_span[b] 与 #cf_span[b'] 相等。
保证答案存在。
输入的第一行包含一个整数 #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'] 的元素。注意，它们之间没有空格。
请输出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[ - 109 ≤ l ≤ r ≤ 109]），满足上述要求。
如果有多个解，输出任意一个即可。
保证答案存在。
在第一个测试用例中，只要满足 #cf_span[6 ≤ l ≤ r ≤ 109]，任意一对 #cf_span[l] 和 #cf_span[r] 都是合法的，此时 #cf_span[b5 = 1]，因为 #cf_span[a1, ..., a5 < l]。
## Input
输入的第一行包含一个整数 #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'] 的元素。注意，它们之间没有空格。
## Output
请输出两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[ - 109 ≤ l ≤ r ≤ 109]），满足上述要求。如果有多个解，输出任意一个即可。保证答案存在。
[samples]
## Note
在第一个测试用例中，只要满足 #cf_span[6 ≤ l ≤ r ≤ 109]，任意一对 #cf_span[l] 和 #cf_span[r] 都是合法的，此时 #cf_span[b5 = 1]，因为 #cf_span[a1, ..., a5 < l]。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 5 \leq n \leq 10^5 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers.
Let $ B' = (b'_1, b'_2, \dots, b'_n) \in \{0,1\}^n $ be a binary string interpreted as a sequence.
Define a transformation parameterized by $ l, r \in \mathbb{Z} $ with $ l \leq r $:
Construct sequence $ B = (b_1, \dots, b_n) $ as:
- $ b_1 = b_2 = b_3 = b_4 = 0 $,
- For $ 5 \leq i \leq n $:
$$
b_i =
\begin{cases}
1 & \text{if } \min(a_1, \dots, a_{i-1}) \geq l \text{ and } \max(a_1, \dots, a_{i-1}) \leq r \\
0 & \text{otherwise}
\end{cases}
$$
**Constraints**
1. $ 5 \leq n \leq 10^5 $
2. $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ b'_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $
4. $ b'_1 = b'_2 = b'_3 = b'_4 = 0 $ (implicit from problem)
**Objective**
Find integers $ l, r \in \mathbb{Z} $ such that $ l \leq r $ and $ B = B' $, i.e.,
$$
\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]
$$
where $ \mathbb{I}[\cdot] $ is the indicator function.
Output any such pair $ (l, r) $.
API Response (JSON)
{
"problem": {
"name": "D. Alena And The Heater",
"description": {
"content": "_\"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 l",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF940D"
},
"statements": [
{
"statement_type": "Markdown",
"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 l...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"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 ≤...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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 bina...",
"is_translate": false,
"language": "Formal"
}
]
}