평균
면접 대비시간 제한1초메모리 제한512 MB
인접한 두 수를 그 평균의 정수 부분으로 바꾸는 연산을 하나가 남을 때까지 반복할 때, 마지막에 얻을 수 있는 가장 큰 수를 구한다.
문제
George는 정보학을 아주 좋아하지만 아직 초보자이므로 여러분의 도움이 필요하다.
정보학 수업에서 선생님은 칠판에 N개의 정수를 적고, George는 여러 번의 연산을 해야 한다. 연산은 인접한 두 정수를 골라 두 수의 산술평균의 정수 부분과 같은 하나의 수로 바꾸는 것이다. 예를 들어 7과 9는 8로, 7과 12는 9로, 101과 102는 101로 바뀐다. George는 칠판에 정수가 하나만 남을 때까지 이 연산을 해야 한다.
George가 마지막에 얻을 수 있는 가장 큰 수를 구하도록 도와주자.
입력
첫째 줄에는 칠판에 적힌 정수의 개수 N이 주어진다.
둘째 줄에는 처음에 칠판에 적힌 N개의 정수 a1, a2, ..., an이 주어진다.
출력
첫째 줄에 모든 연산을 마친 뒤 마지막에 얻을 수 있는 가장 큰 수를 출력한다.
제한
- 1 ≤ N ≤ 200
- 1 ≤ ai ≤ 1,000,000,000 (i는 1부터 N까지)