Bitcoin Profits

Bitcoin is mined by computing a one-way pseudo-random function that outputs a large integer. The network fixes one global difficulty. A block is a claim that new bitcoins were generated, and other participants accept it only when the output of the pseudo-random function meets the difficulty requirement.

Dedicated mining hardware became cheaper, faster and more power efficient, and finding a block with a general-purpose computer soon stopped being feasible. Mining pools appeared instead. Several people donate processing power to a pool, and when the pool finds a block they split the reward in proportion to the work each one contributed.

To measure that proportion, miners work in an arena with a reduced difficulty, for example 1/1048576 of the real difficulty, and submit pool shares. A share that passes the difficulty requirement is assigned a share difficulty taken from the ratio.

To save network bandwidth, a pool member may request a higher base share difficulty, for example 1/524288 of the real difficulty. The reward rises linearly to pay for the extra computation: a share that is $k$ times as hard to find is worth $k$ times the proportional value. Every share with a difficulty below $k$ is discarded. The requested difficulty applies to all shares at once, and a miner cannot pick the best difficulty for each share separately.

You are given the difficulties of the shares a miner earned, as multiples of the base pool difficulty. Find the requested difficulty that would have maximized the reward.

The input holds several test cases. Each test case begins with a line holding the number of accepted shares $N$ ($0 < N < 10^6$). The next line holds $N$ integers $d_1, \dots, d_N$ ($0 \le d_i \le 10^6$), the difficulty of each accepted share as a multiple of the base pool difficulty.

The input ends with a line holding a single zero, and that line is not a test case. The sum of $N$ over all test cases is at most $10^6$.

For each test case print, on its own line, the requested difficulty $k$ that gives the largest reward. Here $k$ is an integer with $k \ge 1$, and the reward for $k$ equals $k$ multiplied by the number of shares whose difficulty is at least $k$.

When several values of $k$ reach the largest reward, print the smallest of them. When every share has difficulty 0, the reward is 0 for every $k$, so print 1.