최댓값 찾기

이 문제는 인터랙티브 문제입니다.

태윤이는 $N$개의 정수 $x_1, x_2,...,x_N$($1 \leq x_i \leq 100\,000$)에 대해 가장 큰 수가 무엇인지 궁금해졌다. 그러나, 모든 수를 전부 보기에는 시간이 오래 걸릴 것 같았기 때문에 신기한 기계를 이용하여 답을 찾고자 한다.

이 기계는 $1$부터 $100\,000$사이의 정수 $t$를 입력하면 $1$부터 $N$까지의 모든 $i$에 대해서 $\vert x_i - t \vert$값의 총합을 반환한다. 다만, 기계가 불완전하기 때문에 $20$번을 넘게 질문하면 터져버린다.

태윤이를 도와 가장 큰 수를 찾아주자.

첫 번째 줄에 수의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$)

기계에는 최대 $20$번까지 질문할 수 있으며 이를 초과할 경우 오답 처리된다.

• ? $t$: 기계에 $t$를 입력한다. 기계는 $\sum_{i=1}^{N}{\vert x_i-t \vert}$을 반환한다. ($1 \leq t \leq 100\,000$)
• ! $t$: $N$개의 수 중 가장 큰 수를 찾아 출력한다. 이는 기계의 질문 횟수에 포함되지 않으며, 출력 후 바로 프로그램을 종료하여야 한다.

각 인터랙션 이후에는 반드시 표준 출력 버퍼를 flush 해 주어야 한다.

언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

채점 시스템은 적응적이지 않다. 즉, 처음에 $x_1, x_2,...,x_N$은 정해져 있으며 상호작용 도중에 바뀌지 않는다.