eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Разбиенеие на две группы

Разбиенеие на две группы

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

С полярниками произошла необычная с исследователями история - о них вспомнили. Плохо, что вспомнили не для того, чтобы пополнить запасы продовольствия и топлива. Вспомнили о них лишь потому, что недалеко решили создать новую станцию, а опытных полярников найти сложно. Вот и решили разбить всех полярников этой станции на две части и одну из них направить на новую станцию. Но возникла проблема: некоторые полярники настолько сблизились друг с другом, что отказываются работать на разных станциях. Все полярники на станции разбились на группы, которые будут работать только вместе или не будут работать вообще. Помогите разделить шрупы полярников на две максимально одинаковые части (т.е. разность количество полярников в частях по модулю должна быть минимальна), не разрывая группы. Обе части должны быть не пустыми.

Вхідні дані

Первая строка содержит N - количество групп людей. Вторая строка содержит N натуральных (целых строго положительных) чисел - количество людей в каждой группе. 2N30000, суммарное количество полярников во всех N группах не превышает 50000.

Вихідні дані

В первой строке необходимо вывести размеры каждой из двух частей.

Во второй и третьей строках необходимо вывести список номеров групп, которые входят в первую и вторую части соотвественно (группы нумеруются в порядке перечисления во входных данных, начиная с единицы). Если существует несколько правильных ответов - выведите любой из них.

Приклад

Вхідні дані #1
5
3 2 5 1 2
Вихідні дані #1
6 7
1 2 4
3 5