Phân chia nhóm tối ưu

Trong một công ty công nghệ lớn, bạn được giao nhiệm vụ tổ chức một hội thảo chuyên đề cho \(N\) nhân viên. Mỗi nhân viên được đánh giá bằng một chỉ số đặc biệt gọi là độ tin cậy (\(a_i\)), biểu thị khả năng thực hiện các nhiệm vụ quan trọng của họ.

Nhiệm vụ của bạn là chia \(N\) nhân viên thành hai nhóm Group A và Group B, với các yêu cầu sau:

• Mỗi nhân viên thuộc đúng một nhóm.
• Sự chênh lệch về tổng độ tin cậy giữa hai nhóm là nhỏ nhất có thể.

Hãy tìm cách phân chia tối ưu và báo cáo giá trị độ chênh lệch nhỏ nhất cũng như số lượng cách phân chia đạt được kết quả này.

Input

Dữ liệu đầu vào gồm:

• Dòng đầu chứa một số nguyên \(N\) \((2 \leq N \leq 32)\), là số nhân viên.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq 10^9)\), là độ tin cậy của các nhân viên.

Output

In ra hai số nguyên \(u\) và \(v\):

• \(u\): độ chênh lệch nhỏ nhất giữa tổng độ tin cậy của hai nhóm.
• \(v\): số lượng cách phân chia đạt được độ chênh lệch nhỏ nhất.

Example

5
1 5 6 7 8

1 3