CuongOnePunch là đại tướng quân của đế chế Byteland hùng mạnh, qua cái tên chúng ta có thể thấy ông là vị dũng tướng bách chiến bách thắng. Hoàng đế __BruteForce__ đã cử CuongOnePunch mang theo toàn bộ đại quân tinh nhuệ đi bình định tộc người man di ở biên giới phía Bắc - một thế lực hùng mạnh đã càn quấy cuộc sống người dân phương Bắc của Byteland hàng thế kỷ qua. Nếu trận chiến này thành công, ông sẽ trở thành người hùng dân tộc được lưu danh sử sách. Ngược lại, sự thất bại của cuộc chiến này sẽ kéo theo sự suy yếu toàn bộ đế chế, tạo tiền đề cho các tiểu vương quốc xung quanh nổi dậy mưu đồ lật đổ, và ông sẽ trở thành tội nhân thiên cổ. Không muốn điều này xảy ra, CuongOnePunch đã bàn bạc với các quân sư và tướng lĩnh để phác thảo nên những chiến lược tốt nhất, nhưng còn một vấn đề vẫn chưa thể giải quyết được, chính là việc phân bố quân đội.

Trong quân có \(N\) vị tướng, người thứ \(i\) chỉ huy \(a_i\) quân sĩ. Vào trận chiến chủ lực sau ba ngày nữa, CuongOnePunch dự định sẽ chia quân thành hai mũi giáp công đánh đồng loạt từ hai phía nhằm xuyên thủng hàng phòng ngự địch. Để chiến lược diễn ra hoàn hảo, sức công phá của hai mũi giáp công này phải mạnh ngang nhau, bởi nếu đánh vào với một mũi mạnh một mũi yếu thì quân địch sẽ dễ dàng phân bố quân đội để phòng thủ. Vậy nên điều cần thiết lúc này là chia \(N\) quân đoàn ra thành hai nhóm sao cho độ chênh lệch số lượng binh sĩ giữa hai nhóm là ít nhất có thể. Đồng thời CuongOnePunch cũng muốn biết có bao nhiêu cách phân chia để đạt độ chênh lệch ít nhất đó, nhằm dễ dàng tùy cơ ứng biến cho mọi tình huống.

Thông thường những vấn đề như này sẽ do Amous xử lý, nhưng hiện tại anh đang phải tịnh dưỡng sau trận đại chiến VOI. Vì đây là vấn đề sống còn của đế chế ByteLand, các bạn hay thay Amous giúp đại tướng quân CuongOnePunch tính phương án chia quân hợp lý nhất nhé! Và lưu ý là không được chia lẻ các đạo quân của các vị tướng quân, hay nói cách khác binh lính dưới trướng vị tướng nào thì chỉ trung thành và tuân lệnh mỗi vị tướng đó. Đồng thời hoán vị giữa hai nhóm chỉ được tính một lần ví dụ cách chia \((1, 3)\) cho nhóm \(1\), \((2, 4)\) cho nhóm \(2\) sẽ tương đương với cách chia \((2, 4)\) cho nhóm \(1\), \((1, 3)\) cho nhóm \(2\).

Input

• Dòng đầu chứa một số nguyên dương \(N\) là số vị tướng quân (hay nói cách khác là số quân đoàn).
• Dòng tiếp theo chứa \(N\) số, số thứ \(i\) là số lượng binh sĩ của quân đoàn thứ \(i\).

Output

• In ra hai giá trị, lần lượt là độ chênh lệch nhỏ nhất có thể đạt được và số cách phân chia.

Ví dụ

Sample input

7
2 5 3 1 6 9 5

Sample output

1 7

Giải thích ví dụ

Độ chênh lệch nhỏ nhất giữa hai nhóm quân là \(1\), có \(7\) cách phân quân cho nhóm quân thứ nhất (biểu diễn bằng chỉ số của các quân đoàn) là \((5, 6)\), \((2, 4, 6)\), \((4, 6, 7)\), \((1, 2, 3, 7)\), \((1, 3, 4, 6)\), \((2, 3, 4, 5)\), \((3, 4, 5, 7)\).

Ràng buộc

• \(n\leq35\).
• \(a_i\leq10^9\).