Addon

Limit pamięci: 32 MB

Addon, nowo odkryty pierwiastek promieniotwórczy jest najwydajniejszym ze znanych paliw jądrowych. Trwają prace nad uruchomieniem energetycznego reaktora addonowego. Projekt przewiduje, że komora paliwowa reaktora będzie miała postać pionowej rury. W komorze jeden na drugim będą ustawione pręty paliwa, czyli walce z addonu. Pręty paliwowe będą produkowane w różnych długościach.

Cykl pracy reaktora rozpoczyna się od wstawienia paliwa do komór. Kolejnym krokiem jest zapłon paliwa. Niestety, wysokość słupa paliwa biorącego udział w reakcji nie może być dowolna, ponieważ tylko dla niektórych wysokości reakcja przebiega bezpiecznie. Wysokości te nazywamy wysokościami stabilnymi.

Projektanci reaktora mają dwa zadania: ustalić wysokość komory paliwowej oraz dobrać zestaw długości, w jakich będą produkowane pręty addonu. Mówimy, że zestaw długości jest bezpieczny dla danej komory, jeżeli wysokość dowolnego słupa, jaki można ustawić w komorze z prętów o długościach z tego zestawu, jest stabilna. Mówimy, że zestaw długości jest pełny dla danej komory, jeżeli z prętów o długościach z tego zestawu można ustawić każdy słup o stabilnej wysokości nie większej niż wysokość tej komory.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia zbiór wysokości stabilnych,
• oblicza maksymalną wysokość komory, dla której istnieje zestaw długości jednocześnie bezpieczny i pełny,
• znajduje dla takiej komory, zestaw długości bezpieczny i pełny, mający minimalną liczbę elementów,
• zapisuje wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana liczba naturalna , . Jest to liczba danych wysokości stabilnych. W każdym z kolejnych wierszy jest zapisana jedna liczba całkowita dodatnia nie większa niż . Są to dane wysokości stabilne zapisane w porządku rosnącym.

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać jedną liczbę — maksymalną wysokość komory. W kolejnych wierszach — rosnący ciąg liczb (każdą w osobnym wierszu) stanowiący wyznaczony zestaw długości.

Przykład

Dla danych wejściowych:

14
5
10
12
15
17
20
21
22
24
26
27
30
31
33

poprawną odpowiedzią jest:

24
5
12
21

Autor zadania: Grzegorz Jakacki.