Производство роботов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Модуль искусственного интелекта GAIA под именем HEPHAESTUS успел сильно развиться и активно занимается производством машин, используя ресурсы системы, в которую встраивается. После того, как Бета выпустила HEPHAESTUS в компьютерную сеть «Далекого Зенита», он сразу составил план по производству $$$n$$$ машин, $$$i$$$-я из которых требует $$$a_i$$$ единиц ресурсов на производство.

Чтобы соптимизировать процесс, ИИ нашел способ сохранять ровно одну единицу ресурсов с каждых $$$100$$$ единиц, задействованных в производстве каждой отдельной машины. Иными словами, с производства машины стоимостью $$$a_i$$$ можно сохранить $$$\left\lfloor \frac{a_i}{100} \right\rfloor$$$ единиц ресурсов.

Желая соптимизировать производство машин еще больше, HEPHAESTUS организовал возможность производить машины в парах. Если произвести машины $$$i$$$ и $$$j$$$ в паре, будет сохранено $$$\left\lfloor \frac{a_i + a_j}{100} \right\rfloor$$$ единиц ресурсов.

Определите, какие машины следует объединить в пары, чтобы сэкономить как можно больше ресурсов. Из всех способов сэкономить наибольшее количество ресурсов следует выбрать тот, в котором как можно меньше машин объединены в пары, и как можно больше произведены самостоятельно.

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

В первой строке ввода записано целое число $$$n$$$ — количество машин, которые надо произвести ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).

Во второй строке через пробел перечислены целые числа $$$a_1$$$, ..., $$$a_n$$$ — количество ресурсов, необходимое для производства каждой машины ($$$1 \leqslant a_i \leqslant 10^9$$$).

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

В первой строке выведите единственное целое число $$$t$$$ — максимальное количество ресурсов, которые можно сэкономить.

Во второй строке выведите целое число $$$k$$$ — минимальное необходимое для этого количество объединений машин в пары.

В следующих $$$k$$$ строках выведите пары номеров машин, которые следует объединить при производстве.

Если возможных ответов с данными $$$t$$$ и $$$k$$$ несколько, выведите любой из них.

Система оценки

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
18$$$n \leqslant 3$$$полная
214все $$$a_i$$$ равны между собойполная
314$$$a_i \leqslant 50$$$ для всех $$$i$$$полная
418$$$n \leqslant 15$$$1полная
520$$$n \leqslant 1000$$$4полная
626нет1 – 5первая ошибка

Примеры

Входные данные
3
30 120 190
Выходные данные
3
1
2 3
Входные данные
6
100 4 197 324 690 500
Выходные данные
18
2
2 3
4 5