Một hôm, hai đứa em họ qua nhà Per chơi. Per định chiêu đãi hai ông cháu loại kẹo rất ngon. Nhưng chia kẹo thế nào đây?

Nhà Per có ~n~ hộp kẹo, hộp thứ ~i~ chứa ~a_i~ chiếc kẹo và không được xé lẻ. Per định chia ~n~ hộp kẹo này làm hai phần, mỗi hộp thuộc về đúng một phần. Do hai đứa nhóc rất so bì nhau nên chênh lệch tổng số kẹo của hai phần phải là nhỏ nhất.

Rất đau đầu trong việc tìm cách chia cho hợp lý, Per đành nhờ sự giúp đỡ của các bạn: hãy tính chênh lệch nhỏ nhất và đếm xem có bao nhiêu cách chia đạt được chênh lệch đó.

Hai cách chia được coi là giống nhau nếu chúng tạo ra cùng một cặp hai phần (không phân biệt phần nào của đứa nào).

Dữ liệu vào

• Dòng đầu chứa số nguyên ~n~ — số lượng hộp kẹo.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ — số lượng kẹo của từng hộp.

Kết quả

In ra hai số nguyên: chênh lệch nhỏ nhất của hai phần và số cách chia đạt được chênh lệch đó.

Ví dụ

Đầu vào:

4
1 5 2 3

Đầu ra:

1 2

Giải thích: Độ chênh lệch ít nhất của hai phần là ~1~. Có ~2~ cách phân chia kẹo (theo chỉ số) là ~(1, 2) - (3, 4)~ và ~(1, 3, 4) - (2)~.

Giới hạn

• ~2 \le n \le 40~
• ~1 \le a_i \le 10^9~

Tổng số kẹo có thể lên tới ~4 \cdot 10^{10}~ nên không thể quy hoạch động theo tổng. Hãy chia ~n~ hộp làm hai nửa, liệt kê tổng của mọi tập con trong từng nửa rồi tìm cặp có tổng gần ~\frac{1}{2}~ tổng chung nhất.