You are given n jars each of which has size s[i]. You are also given an infinite supply of water. In each step you can perform one of the three operations

(i) Fill any jar completely with water

(ii) Empty any jar completely

(iii) Transfer the contents of any one jar to anothe jar till the latter fills completely or the former empties, whichever occurs first.

Your task is to find the minimum no of steps required to obtain x litres of water for all x from 1 to S where S=s[1]+s[2]+..s[n].

note: A litre x can be obtained by combining any numer of jars. For eg. If jar 1 contains 3 litres and jar 2 contains 5 litres, then this is a valid combination for 3,5 and 8 litres as well.

Input:

First line will contain 1 integer, n(1<=n<=5).

The next line will contain n integers denoting s<=s[i]<=9">i.

Output:

Print the minimum no of steps,in order, to obtain x litres of water for all x from 1 to S.

Sample Input:

2

2 4

Sample Output:

-1 1 -1 1 -1 2

Explanation:

Here S=2+4=6. It is impossible to obtain 1,3,or 5 litres from the given jar. 2 or 4 litres can be obtained in 1 step by filling the respectie jars.6 litre can be obtained in 2 steps by filling both jars.