Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему «Умный дом». В соответствующую программу Максим заложил два целых числа tmin ≤ tmax и следующий алгоритм использования обогревателя:
Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения tmin и tmax Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из n дней использования системы.
Максим помнит, что tmin и tmax были целыми числами, по модулю не превосходящими 109 и tmin ≤ tmax, также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал tmin и tmax как можно более близкими друг к другу.
Помогите найти два подходящих значения tmin и tmax, не превосходящих 109 по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из n дней, tmin не превосходит tmax и величина tmax - tmin минимальна.
Гарантируется, что записи программы правильные, и такие два числа существуют.
В первой строке задано целое число n (5 ≤ n ≤ 105) — количество дней, в течение которых работала система.
Во второй строке входных данных задаются n целых чисел t1, ..., tn ( - 109 ≤ ti ≤ 109) — температуры на улице в каждый из n дней.
В третьей строке входных данных задается строка из n символов, состоящая из 0 и 1 — если в i-й позиции данной строки записан 0, то это значит, что в i-й день обогреватель был выключен, а если 1, — то включен.
В единственной строке выведите два целых числа tmin и tmax (tmin ≤ tmax), по модулю не превосходящих 109 — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение tmax - tmin минимально.
Если подходящих пар значений несколько, выведите любую из них.
5
1 2 3 4 5
00001
7 7
11
2 1 -1 -1 1 1 6 7 8 8 6
00000111111
2 6
В первом тестовом примере первые пять дней температура строго меньше 7 градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию 6 ≤ tmin = tmax ≤ 109.
В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования
Решения, работающие при 5 ≤ n ≤ 10, - 10 ≤ ti ≤ 10, наберут не менее 20 баллов.
Решения, работающие при 5 ≤ n ≤ 100, - 100 ≤ ti ≤ 100, наберут не менее 40 баллов.
Решения, работающие при 5 ≤ n ≤ 100, - 109 ≤ ti ≤ 109, наберут не менее 60 баллов.