Cho N người(2≤N≤32) ,mỗi người có một số ai(1 ≤ ai ≤ 10^9) được gọi là độ tin cậy

Cần phân chia n người này vào 2 tập sao cho:

• Mỗi người thuộc đúng một tập
• Chênh lệch tổng độ tin cậy của 2 phần là bé nhất

Input

Dòng đầu chứa số nguyên N Dòng tiếp theo chứa N số : số thứ i là độ tin cậy của người thứ i

Output

Ghi ra hai số u và v với u là độ chênh lệch nhỏ nhất và v là số cách phân chia

Example

Input
5   
1 5 6 7 8

Output
1 3  

Chú thích: Độ chênh lệch ít nhất của 2 phần là 1
Có 3 cách phân chia .3 cách phân chia nhóm 1 là (3,5) ,(1,3,4) và (1,2,5)