애드온

과학자들이 새로운 방사성 원소인 애드온(addon)을 발견했습니다. 애드온은 지금까지 알려진 것 중 가장 효율적인 핵연료였고, 그래서 애드온 원자로를 만들기로 했습니다. 설계상 연료 격실은 수직으로 세워진 관입니다. 연료봉, 즉 애드온으로 된 원기둥을 이 관 안에 하나씩 위로 쌓아 넣습니다. 연료봉의 길이는 여러 가지일 수 있습니다.

원자로의 한 주기는 격실에 연료봉을 넣는 것으로 시작해서, 다음으로 점화를 합니다. 그런데 쌓아 올린 연료 기둥의 높이는 아무 값이나 되어서는 안 됩니다. 특정한 높이일 때만 반응이 안전하며, 그런 높이를 안정 높이라고 부릅니다.

설계자는 두 가지를 정해야 합니다. 하나는 연료 격실의 높이이고, 다른 하나는 생산할 애드온 연료봉의 길이 집합입니다. 어떤 길이 집합이 (주어진 격실에 대해) 안전하다는 것은, 그 집합에 속한 길이의 연료봉만으로 쌓고 격실 높이를 넘지 않는 모든 기둥의 높이가 항상 안정 높이라는 뜻입니다. 어떤 길이 집합이 (주어진 격실에 대해) 완전하다는 것은, 격실 높이를 넘지 않는 모든 안정 높이의 기둥을 그 집합의 길이만으로 쌓아 만들 수 있다는 뜻입니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 안정 높이들의 집합을 읽고,
• 안전하면서 완전한 길이 집합이 존재하는 격실의 최대 높이를 구하고,
• 그 격실에 대해 안전하고 완전하면서 원소 개수가 가장 적은 길이 집합을 찾아,
• 결과를 표준 출력에 씁니다.

첫 번째 줄에는 주어진 안정 높이의 개수인 자연수 $n$이 있습니다 ($1 \le n \le 10\,000$). 이어지는 $n$개의 줄에는 각각 하나의 양의 정수가 있으며, 그 값은 $10\,000$을 넘지 않습니다. 이 수들은 안정 높이이고 증가하는 순서로 주어집니다.

첫 번째 줄에는 정수 하나, 즉 격실의 최대 높이를 출력합니다. 이어지는 줄들에는 계산한 길이 집합을 증가하는 순서로 한 줄에 하나씩 출력합니다.