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

Cần phân chia \(n\) người này vào 2 nhóm sao cho:

• Mỗi người thuộc đúng một nhóm
• Chênh lệch tổng độ tin cậy của 2 nhóm 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.

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(N \le 24\).
• Subtask \(2\) (\(20\%\) số điểm): không có điều kiện gì thêm

Example

5
1 5 6 7 8

1 3