409461: GYM103566 I Башни из спичек

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

Жил-был Вовочка. Однажды дома он нашел спички и от нечего делать решил построить из них Башню, очень особенную. Правда так и не придумал, что именно особенного будет в его Башне.

На следующий день случилось чудо. Папа мальчика работал на Балабановской спичечной фабрике и решил взять его с собой на работу. В кабинете, где он сидел, было полно спичек разных длин. В углу Вовочка заметил книжку с надписью «ГОСТ». Книжка была толстая, нашлись в ней и требования к башне из спичек:

1. Башней называется построение из равных между собой прямоугольников  — у всех прямоугольников должны быть одинаковая ширина и одинаковая высота;
2. Этажом башни называется один прямоугольник;
3. Спичка, являющаяся потолком одного этажа, одновременно является полом следующего этажа  — к примеру, башня из двух этажей состоит из $$$7$$$ спичек ($$$3$$$ в ширину и $$$4$$$ в высоту);
4. Ширина и высота этажа должны совпадать с длиной ровно одной спички, используемой в качестве стены / пола / потолка;
5. Высотой башни называется произведение количества этажей на высоту одного этажа.
6. Корректная башня содержит хотя бы $$$1$$$ этаж.

Маленький мальчик сразу понял, что его Башня будет самой высокой! Правда тут же у Вовочки возник вопрос  — а какую максимальную высоту может иметь построенная им Башня? Мальчик еще не знает, что такое «произведение», поэтому просит вас помочь ему в этом деле.

Помогите Вовочке вычислить максимальную высоту Башни, которая может быть построена из имеющихся у мальчика спичек.

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

В первой строке вводится одно число $$$N$$$ $$$(1 \leq N \leq 200000)$$$  — количество спичек. Во второй строке записаны $$$N$$$ целых чисел $$$A_i$$$ $$$(1 \leq A_i \leq 200000)$$$ через пробел  — длина $$$i$$$-й спички.

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

Выведите через пробел $$$3$$$ целых числа  — количество этажей, высоту одного этажа и его ширину. Если существует несколько башен с максимальной высотой, выведите любую. Если ни одну башню составить не получается, выведите $$$3$$$ раза через пробел $$$-1$$$.

ПримерыВходные данные

4
5 5 5 5

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

1 5 5

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

7
4 4 8 4 8 4 8

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

1 8 4

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

5
1 2 3 4 3

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

-1 -1 -1

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

10
5 5 5 5 5 5 7 7 7 5

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

2 5 7

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

7
1 1 2 3 3 3 3

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

1 3 1

Примечание

Пояснения к тестам из условия.

1. В тесте $$$1$$$ можно построить башню, состоящую из одного квадрата $$$5 \times 5$$$.
2. Во втором тесте подходят $$$2$$$ башни. Первая состоит из $$$2$$$ прямоугольников $$$4$$$ в высоту, $$$8$$$ в ширину. Вторая  — из одного прямоугольника $$$8$$$ в высоту, $$$4$$$ в ширину. Высота обеих башен  — $$$8$$$, а значит любая из них будет являться правильным ответом.
3. В третьем тесте не получается составить ни одного прямоугольника, поэтому ответ $$$-1$$$.
4. В четвертом тесте оптимальной башней является построение из двух прямоугольников со сторонами $$$5 \times 7$$$ или двух квадратов $$$5 \times 5$$$.
5. В пятом тесте можно построить только следующие башни:
   • один этаж высотой $$$3$$$ и шириной $$$1$$$  — оптимальная;
   • один этаж высотой $$$1$$$ и шириной $$$3$$$  — неоптимальная;
   • один этаж высотой $$$3$$$ и шириной $$$3$$$  — оптимальная.