Задача Prize

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

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

Під час одного з розіграшів сума виграшу була найбільшою з усіх можливих для даних ставок. Знайдіть цю суму та номери учасників, що отримали виграш.

Технічні умови. Програма Prize читає  число N (4≤N≤10000), а в наступному рядку  N чисел  k₁,  k₂, … , k_N,  де k_i – номер учасника розіграшу, що зробив ставку на  i-й стержень. Всі числа розділено пропусками.

Програма виводить на екран суму виграшу  а далі у наступному рядку  виграшні номери учасників у порядку зростання. Всі числа розділено пропусками

Приклад.

Введення:    

9

2  8  5  3  6  1  9  7  4

Виведення:   

29

2  4  6  8  9