Alena And The Heater

给出两个长度为N的数组A，B，以及一种计算规律： 若t[i]=1，需满足t[i-1]=t[i-2]=t[i-3]=t[i-4]=0，以及max{A[i],A[i-1],A[i-2],A[i-3],A[i-4]} < l 若t[i]=0，需满足t[i-1]=t[i-2]=t[i-3]=t[i-4]=1，以及min{A[i],A[i-1],A[i-2],A[i-3],A[i-4]} > r 其他情况:t[i]=t[i-1]（|l|,|r|≤10^9） 现在要使得运算一次的结果t=B，求满足条件的l,r（保证有解） N≤100000

"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}&gt;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}&lt;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.

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

5
1 2 3 4 5
00001

6 15

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

-5 5

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}&lt;l $ .