Cho ~N~ người ~\left(2 \leq N \leq 32\right)~, mỗi người có một số ~a_{i}~ ~\left(1 \leq a_i \leq 10^9\right)~ đượ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

Sample Input

5
1 5 6 7 8

Sample Output

1 3

Note

Độ chênh lệch ít nhất của ~2~ phần là ~1~.

Có ~3~ cách phân chia nhóm ~1~ là ~(3,5)~, ~(1,3,4)~ và ~(1,2,5)~