ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

УрКОП 2020

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Интересные разговоры

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Алиса и Боб любят принимать у себя гостей, а особенно любят слушать, о чем говорят их гости между собой. Сегодня у Алисы праздник — она в очередной игре победила Боба при том, что он играл оптимально. Это ли не повод отпраздновать?
На праздник Алиса позвала n друзей, которых рассадила за круглым столом и пронумеровала их по часовой стрелке от 1 до n. Для каждого друга Алиса определила его интересность целым положительным числом ai. Как только все расселись за столом, друзья начали общаться между собой, при том только с теми, кто сидит непосредственно слева или справа от них. Чтобы понять, какие разговоры стоит слушать, а какие нет, Алиса определила интересность i-го разговора как |aiai+1| при 1≤ i < n и как |ana1| при i=n. Чем это значение больше, тем разговор интереснее.
Теперь, чтобы снова не расстроить Боба и при этом получить удовольствие от подслушивания, Алиса хочет разделить все разговоры на два непустых множества так, чтобы каждый разговор попал только в одно множество и суммарные интересности разговоров в каждом множестве были равны. Помогите Алисе найти эти множества.

Исходные данные

Первая строка содержит одно целое число n (3 ≤ n ≤ 100000).
Вторая строка содержит n целых чисел a1, a2, …, an — интересности друзей (1 ≤ ai ≤ 109).

Результат

В первой строке выведите «YES», если разговоры можно разбить на два множества так, как хочет Алиса, или «NO» в противном случае. В случае «NO» дальше выводить ничего не нужно.
Во второй строке выведите m — размер первого множества.
В третьей строке выведите через пробел p1, p2, …, pm — номера разговоров в первом множестве.
В четвертой строке выведите k — размер второго множества.
В пятой строке выведите через пробел q1, q2, …, qk — номера разговоров во втором множестве.

Пример

исходные данныерезультат
3
1 2 3
YES
2
1 2 
1
3
Автор задачи: Семён Трифочкин
Источник задачи: Уральская командная олимпиада по программированию 2020
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2156. Интересные разговоры