문제

진흥이는 개의 동전을 가지고 있습니다. 번째 동전의 가치는 양의 정수 입니다.

물건의 가격이 양의 정수로 주어질 때, 개 이상의 동전을 골라 그 가치의 합이 물건의 가격과 일치하게 만들 수 있으면 진흥이는 그 물건을 살 수 있습니다.

부터 까지의 각 정수 에 대해서, 진흥이가 첫 번째 동전부터 번째 동전까지만 고를 수 있는 경우에 살 수 없게 되는 물건의 가장 낮은 가격을 구해 봅시다.

입력

첫 번째 줄에 전체 동전의 개수 이 주어집니다.

두 번째 줄에 각 동전의 가치를 나타내는 정수 이 공백으로 구분되어 주어집니다.

출력

개의 줄에 걸쳐 문제의 답을 출력합니다. 번째 줄에는 진흥이가 첫 번째 동전부터 번째 동전 중에서만 고를 수 있는 경우에 살 수 없게 되는 물건의 가장 낮은 가격을 출력합니다.

노트