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