막심의 트라이앵글
면접 대비시간 제한2초메모리 제한512 MB
일련의 탐침 주파수와 각 주파수가 미지의 값에 더 가까운지 먼지를 나타내는 기록이 주어질 때, 미지의 값이 될 수 있는 최솟값과 최댓값을 구한다.
문제
막심은 어릴 때부터 음악에 재능이 있었고 손재주도 좋았다. 최근에는 간단한 타악기인 트라이앵글을 직접 만들었다. 그는 이 악기에서 나는 소리의 주파수가 얼마인지 알아내려 한다.
막심에게는 지정한 주파수의 음을 재생할 수 있는 전문 음악 튜너가 있다. 막심은 다음과 같이 행동한다. 튜너에서 서로 다른 주파수의 음을 켜고, 각 음마다 그 음이 트라이앵글 소리에 이전 음보다 더 가까운지 더 먼지를 귀로 판단한다. 막심은 절대음감이 있어서 이 판단을 항상 정확하게 한다.
막심은 튜너에 설정한 주파수들의 수열과, 두 번째 음부터 각 음이 이전 음보다 트라이앵글 소리에 더 가까운지 더 먼지를 적은 기록을 보여 주었다. 막심의 트라이앵글 소리 주파수는 30헤르츠 이상 4000헤르츠 이하라는 것을 미리 알고 있다.
트라이앵글 소리 주파수가 있을 수 있는 구간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 막심이 튜너로 재생한 음의 개수 이 정수로 주어진다 (). 다음 개 줄에는 막심의 기록이 주어지며, 각 줄은 두 요소로 이루어진다. 실수 는 튜너에 설정한 주파수(헤르츠)이고 (), 첫 번째 주파수를 제외한 각 주파수에는 단어 closer 또는 further가 따라온다.
closer는 이 음의 주파수가 이전 음의 주파수보다 트라이앵글 소리 주파수에 더 가깝다는 뜻이며, 형식적으로는 로 나타낼 수 있다.
further는 이 음의 주파수가 이전 음보다 더 멀다는 뜻이다.
어떤 음이 트라이앵글 소리에 이전 음만큼 가깝다면, 막심은 위의 두 단어 중 아무거나 적을 수 있었다.
막심이 얻은 결과는 모순이 없다고 보장된다.
출력
막심이 만든 트라이앵글 소리 주파수의 가능한 최솟값과 최댓값을 공백으로 구분해 출력한다.