"Мы пробовали одиночное заключение, утопление и прослушивание группы Just In Beaver, но безрезультатно. Нам нужно что-то экстремальное."
"Маленькой Алене подарили массив на день рождения..."
Пусть есть массив a длиной n и два числа l и r (l ≤ r). Тогда массив b имеет размер n и получается следующим образом:
b1 = b2 = b3 = b4 = 0.
Для всех 5 ≤ i ≤ n:
- bi = 0 если ai, ai - 1, ai - 2, ai - 3, ai - 4 > r и bi - 1 = bi - 2 = bi - 3 = bi - 4 = 1
- bi = 1 если ai, ai - 1, ai - 2, ai - 3, ai - 4 < l и bi - 1 = bi - 2 = bi - 3 = bi - 4 = 0
- bi = bi - 1 иначе
Даны массивы a и b' одинакового размера. Найдите числа l и r (l ≤ r) такие, что применив описанный выше алгоритм, мы получим массив b, равный массиву b'.
Гарантируется, что ответ существует.
Выходные данные
В единственной строке выведите два целых числа l и r ( - 109 ≤ l ≤ r ≤ 109), удовлетворяющие условиям, описанным выше.
Если подходящих пар значений несколько, выведите любую из них.
Гарантируется, что ответ существует.
Примечание
В первом тестовом примере подходит любая пара l и r, где 6 ≤ l ≤ r ≤ 109, в таком случае b5 = 1, так как a1, ..., a5 < l.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
00001
|
6 15
|
|
2
|
10
-10 -9 -8 -7 -6 6 7 8 9 10
0000111110
|
-5 5
|