P5941 [POI 1997] ADDON

Scientists have discovered a new radioactive element, `ADDON`. `ADDON` is the most efficient nuclear fuel known, so they decided to build an `ADDON` nuclear reactor.

According to the plan, a fuel chamber is a vertical tube. Fuel rods (i.e., cylinders filled with `ADDON`) are put into the fuel chamber one on top of another, forming a column. Fuel rods can have different heights. A reactor cycle starts with placing fuel rods into the fuel chamber. The next step is ignition. The troublesome part is that the column height cannot be arbitrary—only certain specific heights can guarantee that the reaction is safe. Such heights are called stable heights. Now the reactor designers face two tasks: determine the height of the fuel chamber and choose a set of heights for manufacturing `ADDON` fuel rods. We say a set of heights is safe (for a fuel chamber of a fixed height) if: - For any column built from fuel rods whose heights belong to this set, and whose total height does not exceed the fuel chamber height, the total height must be a stable height. We say a set of heights is complete (for a fuel chamber of a fixed height) if: - For any column whose height is stable and does not exceed the fuel chamber height, it must be possible to build it using fuel rods whose heights belong to this set. Now write a program to: - 1. Read a set of stable heights. - 2. Find the maximum possible fuel chamber height for which there exists a height set that is both safe and complete. - 3. For the fuel chamber height found, find a safe and complete height set with the minimum number of elements. - 4. Output the result.

The first line contains a natural number $n$, representing the number of given stable heights. Each of the next $n$ lines contains a positive integer not exceeding $10000$. These numbers are given in increasing order and represent the stable heights.

The first line contains the maximum possible fuel chamber height found. Each of the following lines outputs, in increasing order, one element of the height set you found.

For $100\%$ of the testdata, $1\le n\le10000$. Translated by ChatGPT 5