Centre for Gifted Education - Hanoi university of Technology

Giải thuật tham lam (tiếng Anh: Greedy algorithm) là một thuật toán giải quyết một bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục.

Nếu nói theo 1 cách dễ hiểu thì khi bắt gặp 1 bài toán không có thuật toán tốt hoặc bạn chưa nhìn ra được thuật toán tốt. Bạn nghĩ ngay đến 1 phương pháp cho kết quả tiệm cận kết quả tối ưu. Tất nhiên tốt như thế nào thì tuỳ từng giải thuật của bạn.

Xét bài toán sau:

2 anh em Chip và Dale được bác Zone tặng cho n gói kẹo. Gói kẹo thứ i có A_i cái. Chip và Dale đang cãi nhau vì không biết nên chia như thế nào cho công bằng. Vì thế Chip & Dale nhờ bác Zone chiâ những gói kẹo thành 2 phần sao cho chênh lệnh số kẹo của 2 phần là bé nhất.

Input

Dòng 1: ghi số nguyên N là số gói kẹo

Dòng thứ 2 gồm n số A_i, số thứ i là số kẹo trong gói thứ i.

Output

Dòng 1: ghi số nguyên S là số kẹo chênh lệch trong 2 cách chia.

Dòng 2: Ghi chỉ số các gói kẹo Chip được chia.

Dòng 3: Ghi chỉ số các gói kẹo Dale được chia.

Vì bài này không có thuật toán tốt do đó. Trong trường hợp kết quả của bạn không tối ưu, bạn vẫn sẽ nhận được 1 số điểm nếu kết quả đó không quá tầm thường

Example

Input:
5
10 20 30 40 50

Output:
10
1 2 4
3 5

Giới hạn:
1 <= n <= 10
1 <= Ai <= 100