Качели в игровом зале

В игровом зале стоят большие призовые качели: два сиденья и табло, которое показывает разницу веса между левым и правым сиденьем.

После турнира вы выиграли n призов. У каждого приза есть «вес» (целое число). Призы нужно разложить по двум сиденьям (каждый приз — ровно на одно сиденье), чтобы разница суммарных весов была как можно меньше.

Чтобы ведущий не спорил с вами, договоримся о каноническом ответе:

• мы выводим индексы призов (нумерация с 1), которые кладём на левое сиденье;
• среди всех раскладок с минимальной возможной разницей выбираем ту, где суммарный вес левого сиденья не превосходит суммарный вес правого;
• если и таких несколько, выбираем раскладку с лексикографически минимальным списком индексов левого сиденья (индексы внутри списка идут по возрастанию).

Формат ввода

Первая строка: целое число n. Вторая строка: n целых чисел a1, a2, ..., an — веса призов.

Формат вывода

В первой строке выведите одно целое число — минимальную возможную разницу между суммами весов на двух сиденьях. Во второй строке выведите число k — сколько призов на левом сиденье, а затем k индексов этих призов в возрастающем порядке (канонический выбор по правилам выше).

Ограничения

• 1 ≤ n ≤ 20
• 1 ≤ ai ≤ 1 000 000

Пример

Ввод:

4
10 7 6 5

Вывод:

2
2 2 3

В этом примере на левое сиденье кладём призы с весами 7 и 6 (индексы 2 и 3), на правое — 10 и 5. Разница равна 2, и это минимум.

Ключевое наблюдение: раскладка однозначно задаётся выбором множества призов для левого сиденья. Тогда правая сумма — это total - left, а разница равна abs(total - 2*left). По правилу каноничности нам нужны только варианты с left <= right, то есть left <= total//2 — это сразу режет половину перебора.

Почему работает перебор: n <= 20, значит подмножеств 2^n всего до 1 048 576 — это реально посчитать в лоб.

План:

• Считай total = sum(a) и half = total // 2.
• Иди по всем mask от 0 до (1<<n)-1.
• Для каждого mask посчитай left (сумму весов тех i, где бит 1).
• Если left > half, пропусти (иначе нарушим left <= right).
• Посчитай разницу: diff = total - 2*left (она неотрицательна из-за фильтра).
• Обновляй лучший ответ:
• берём меньший diff;
• при равном diff выбираем лексикографически минимальный список индексов слева (индексы по возрастанию).
• В конце выведи best_diff и сам список индексов.

Сложность: O(n * 2^n) по времени и O(1) доп. памяти (кроме хранения ответа).

Частая ошибка: сравнивать лексикографически «маски» или строки, а не списки индексов. Правильнее сравнивать именно последовательности индексов слева (например, [2,3] < [2,4], а [2,3] < [2,3,5]).