시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB253907843.820%

문제

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

태윤이는 $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$은 정해져 있으며 상호작용 도중에 바뀌지 않는다.

예제 입력 1

5

4

1

예제 출력 1


? 1

? 2

! 2

예제는 이해를 돕기 위해 의도적으로 빈 줄을 추가한 것으로 실제 입출력에는 빈 줄이 나타나지 않는다.

위의 예제는 주어진 수가 $1, 2, 2, 2, 2$일 때의 입출력이다.

첫 번째 쿼리인 ? $1$에 대해 채점 시스템은 ${\vert 1-1 \vert + 4 \times\vert 2-1 \vert}$의 값인 $4$를 출력한다.

두 번째 쿼리인 ? $2$에 대해 채점 시스템은 ${\vert 1-2 \vert + 4 \times\vert 2-2 \vert}$의 값인 $1$을 출력한다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.