В столице Алгосов открылся новый ресторан. Для привлечения клиентов в нём действует система скидок по купонам.
При каждой покупке более чем на 500 рублей клиент получает купон. Этот купон даёт право на один бесплатный обед. Гоша решил обедать там каждый день в течение n дней, причём каждый день он будет покупать ровно один обед. Гоша изучил прейскурант на ближайшие n дней. Он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны.
Требуется найти минимальную возможную суммарную стоимость обедов и номера дней, в которые Гоше следует воспользоваться купонами.
В первой строке записано целое число n (1 ≤ n ≤ 1000). В следующих n строках записано n чисел – стоимости обеда в каждый из дней (по одному в строке). Стоимость обеда лежит в диапазоне от 1 до 1000.
Выведите суммарную стоимость, которую заплатит Гоша, и сколько купонов он потратит при этом. В следующей строке выведите в возрастающем порядке номера дней, когда надо использовать купоны.
Если возможно несколько вариантов ответа, то выведите любой.
|
3 500 501 300 |
1001 1 3 |
|
4 502 501 503 504 |
1003 2 3 4 |