비트코인 수익

비트코인은 큰 정수를 출력하는 단방향 유사난수 함수를 계산해서 채굴한다. 네트워크 전체에 난이도가 하나 정해져 있고, 블록은 비트코인을 새로 생성했다는 주장이다. 유사난수 함수의 출력이 난이도 조건을 만족할 때만 다른 참가자가 그 블록을 받아들인다.

전용 채굴 장비가 더 싸고 빠르고 전력 효율도 좋아지면서 범용 컴퓨터로 블록을 찾는 일은 곧 불가능해졌다. 대신 채굴 풀이 생겼다. 여러 사람이 풀에 연산 능력을 내놓고, 풀이 블록을 찾으면 각자 기여한 작업량의 비율대로 보상을 나눈다.

이 비율을 재려고 채굴자는 실제 난이도보다 낮은 무대, 예를 들어 실제 난이도의 1/1048576에서 채굴하며 풀 지분을 제출한다. 난이도 조건을 넘긴 지분에는 그 비율에서 계산한 지분 난이도가 매겨진다.

네트워크 대역폭을 아끼려고 풀 참가자는 기본 지분 난이도를 더 높게, 예를 들어 실제 난이도의 1/524288로 요청할 수 있다. 늘어난 연산량은 보상을 선형으로 올려서 메운다. 찾기가 $k$배 어려운 지분에는 비례 배분값의 $k$배를 준다. 난이도가 $k$보다 낮은 지분은 모두 버린다. 요청한 난이도는 모든 지분에 한꺼번에 적용되고, 채굴자가 지분마다 최적의 난이도를 따로 고를 수는 없다.

채굴자가 얻은 지분의 난이도가 기본 풀 난이도의 배수로 주어진다. 보상을 가장 크게 만드는 요청 난이도를 구하여라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 받아들여진 지분의 개수 $N$이 주어진다 ($0 < N < 10^6$). 다음 줄에는 각 지분의 난이도 $d_1, \dots, d_N$이 기본 풀 난이도의 배수로 주어진다 ($0 \le d_i \le 10^6$).

입력의 마지막 줄에는 0 하나만 주어지며, 이 줄은 테스트 케이스가 아니다. 모든 테스트 케이스의 $N$의 합은 $10^6$ 이하이다.

각 테스트 케이스마다 보상이 가장 큰 요청 난이도 $k$를 한 줄에 하나씩 출력한다. $k$는 1 이상의 정수이고, $k$의 보상은 난이도가 $k$ 이상인 지분의 개수에 $k$를 곱한 값이다.

보상이 가장 큰 $k$가 여럿이면 그중 가장 작은 값을 출력한다. 모든 지분의 난이도가 0이면 어떤 $k$를 골라도 보상이 0이므로 1을 출력한다.