Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Prize

Задача Prize Для розыгрыша денежных призов использовали игровой аппарат, конструкция которого состоит из вертикально размещенного плоского основания и прикрепленных перпендикулярно к нему N стержней (N – квадрат некоторого натурального числа), пронумерованных от 1 до  N (размещение и нумерация стержней показаны на рисунке). Корпус игрового аппарата ограничивает движение шарика так, что его путь обязательно начинается с первого стержня и заканчивается на последнем. 

В розыгрыше участвуют ровно N участников, каждый из которых получает свой оригинальный номер (от 1 до  N) и перед началом розыгрыша делает ставку, прикрепляя карточку со своим номером к одному из стержней, каждый к своему. Розыгрыш проводят, впуская шарик сверху в игровой аппарат. Стержни, на которые шарик во время свого движения падает вертикально вниз, считаются выигрышными, то есть, выигрышными являются номера участников, сделавших ставку на эти стержни, а сумма выигрыша равна сумме выигрышных номеров участников розыгрыша (см. рисунок).

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

Технические условия. Программа Prize читает число N (4≤N≤10000), а в следующей строке N чисел  k1,  k2, … , kN,  де kiномер участника розыгрыша, сделавшего ставку на  i-й стержень. Все числа разделены пробелами.

Программа выводит на экран сумму выигрыша,  а далее в следующей строке  выигрышные номера участников в порядке возрастания. Все числа разделены пробелами

Пример.

Ввод:  

9

2  8  5  3  6  1  9  7  4

Вывод:  

29

2  4  6  8  9


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"