Có n gói kẹo. Gói thứ i có A[i] viên kẹo.

Không bóc các gói kẹo, hãy tìm cách chia hết các gói kẹo thành 2 phần sao cho tổng số viên kẹo của các phần gần bằng nhau nhất, hay nói cách khác, độ chênh lệnh của tổng viên kẹo của 2 phần là nhỏ nhất.

Input

• Dòng 1: Số n
• Dòng 2: n số nguyên dương A1, A2,..., An

Output

• Dòng 1: Độ chênh lệch nhỏ nhất của số viên kẹo của 2 phần.
• Dòng 2: Chỉ số các gói kẹo chia vào phần thứ nhất
• Dòng 3: Chỉ số các gói kẹo chia vào phần thứ hai

Ghi ra một phương án bất kì.

Ví dụ

Input

5
4 7 9 3 3

Output

0
1 3
2 4 5

Input

4
3 10 3 2

Output

2
1 3 4
2

Ràng buộc:

• Subtask 1: n ≤ 100; Ai ≤ 1000;
• Subtask 2: n ≤ 1000; Ai ≤ 100;