Задача 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