Nuclear Reactor Fuel Configuration

A nuclear reactor is designed such that its fuel chamber is a vertical tube. Fuel rods (cylinders containing an ADDON) are stacked one on top of the other to form a cylinder. Each fuel rod has a certain height. However, not every total height of a cylinder is acceptable. Only certain heights guarantee that the reactor operates safely; these heights are called stable heights.

The reactor design requires you to perform two tasks for a given set of stable heights S:

1. Determine the fuel chamber height H (which must itself be a stable height) with the maximum possible value such that there exists a set D of fuel rod heights with the following two properties:
2. Safety: For any collection of rods (each having a height from D) that can be stacked to form a cylinder with total height not exceeding H, the resulting height must be stable (i.e. must belong to S).
3. Completeness: Every stable height not exceeding H can be obtained by stacking rods whose heights come from D (rods may be used in unlimited quantities).

Mathematically, if rods of heights d₁, d₂, …, d_k are chosen from D, then the safety requirement is:

$$\text{If } \sum_{i=1}^{k} d_i \le H \text{ then } \sum_{i=1}^{k} d_i \in S. $$

The completeness requirement is:

$$\forall s \in S \text{ with } s\le H, \quad \exists \ d_1, d_2, \ldots, d_k \in D \text{ such that } \sum_{i=1}^{k} d_i = s.$$</p>

Your job is to:

1. Read in a set S of stable heights.
2. Find the maximum possible fuel chamber height H (which must be an element of S) for which there exists a safe and complete set of fuel rod heights D.
3. For that chamber height H, determine a safe and complete set D that uses the fewest number of distinct rod heights.
4. Output H and the set D.

Important note: Since any fuel rod in D must be stable and any rod combination (if its total does not exceed H) must yield a stable height, it turns out that a safe and complete rod set exists only when the stable heights up to H form a continuous sequence starting from 1. In other words, if the input set S (which may be unsorted) does not contain 1 or misses any integer between 1 and a candidate H, then no safe and complete rod set exists for that H. Hence, the maximum possible H is the largest integer such that all numbers from 1 to H are stable.

Once H is determined, the minimal rod set D can be constructed using a greedy strategy. Start with a current representable sum curr = 0 and repeatedly choose the rod of height curr + 1 (which is guaranteed to be stable). After adding this rod, update curr to curr + (curr + 1). Continue until curr reaches or exceeds H. This set D is guaranteed to be safe (no unstable height up to H can be formed) and complete (every stable height from 1 to H is representable).

## inputFormat

The first line contains an integer n, the number of stable heights. The next line (or lines) contains n integers representing the stable heights. The stable heights may be given in any order.

## outputFormat

Output two lines:

• The first line contains the maximum possible fuel chamber height H.
• The second line contains the safe and complete rod set D (with the minimum number of elements) used to build any height up to H. Output the elements of D separated by a single space. If no safe and complete configuration exists (i.e. if 1 is not stable), output 0 on the first line and leave the second line empty.

## sample

8
1 2 3 4 5 6 7 8

8
1 2 4 8

$$