A1. Милая сердцу Бобрунья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

— О, милая сердцу Бобрунья, не желаете ли вы прогуляться со мной по расчудесной лесополосе?

— Конечно, мой Умный Бобр, давайте насладимся прекрасными видами вместе. Как насчет вечера пятницы?

Умный Бобер засуетился. К пятнице все должно быть идеально, поэтому срочно нужно подготовить лесополосу к предстоящей прогулке — выпилить некоторые деревья.

Рассмотрим лесополосу как последовательность деревьев. Каждое дерево i характеризуется своей эстетической привлекательностью ai — одни деревья очень красивы, другие так себе, а третьи даже пугают своим внешним видом!

Умный Бобер вычислил, что для завоевания сердца Бобруньи нужно добиться следующих эффектов:

  • во-первых, Бобрунью нужно порадовать: сумма эстетических привлекательностей оставшихся в лесополосе деревьев должна быть максимально возможной;
  • во-вторых, Бобрунью нужно удивить: эстетические привлекательности первого и последнего деревьев лесополосы должны быть равны;
  • ну и, конечно, прогулка должна состояться: нужно оставить хотя бы два дерева в лесополосе.

Теперь помогите Умному Бобру! Какие деревья придется выпилить для завоевания сердца Бобруньи?

Входные данные

В первой строке содержится единственное целое число n — изначальное количество деревьев в лесополосе, 2 ≤ n. Во второй строке через пробел перечислены целые числа ai — эстетические привлекательности каждого из деревьев. Все эстетические привлекательности не превосходят 109 по модулю.

  • для получения 30 баллов требуется решить задачу при n ≤ 100 (подзадача A1);
  • для получения 100 баллов требуется решить задачу при n ≤ 3·105 (подзадачи A1+A2).
Выходные данные

В первой строке выведите два целых числа — суммарную эстетическую привлекательность лесополосы после ее обработки Умным Бобром и количество выпиливаемых деревьев k.

В следующей строке выведите k чисел — номера деревьев, которые стоит выпилить. Считайте, что деревья пронумерованы от 1 до n слева направо.

Если существует несколько решений, то выведите любое из них. Гарантируется, что хотя бы два дерева имеют одинаковую эстетическую привлекательность.

Примеры
Входные данные
5
1 2 3 1 2
Выходные данные
8 1
1
Входные данные
5
1 -2 3 1 -2
Выходные данные
5 2
2 5