Giải bài trực tuyến

Cho N người(2≤N≤32) ,mỗi người có một số a_i(1 ≤ a_i ≤ 10⁹) đượ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)