n человек подошли ночью к реке. Имеется узкий мост, который одновременно может вместить только двух человек. У них есть один фонарик, и, поскольку сейчас ночь, при переходе через мост его необходимо использовать. Движение по мосту без фонаря запрещено.

Для каждого человека известно время, за которое он пересекает мост. Если по мосту двигаются двое, то время их передвижения равно времени более медленного. Необходимо найти минимальное время, за которое все n людей перейдут на другой берег реки, а также последовательность переходов, как указано в примере.

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

Состоит из нескольких тестов. Первая строка каждого теста содержит количество людей n (n ≤ 1000), а вторая строка содержит n чисел - время перехода людей через мост. Время перехода каждого человека через мост не более 10000 секунд.

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

Для каждого теста вывести следующую информацию. Первая строка содержит минимальное время в секундах, за которое могут пересечь мост n людей. Далее следует стратегия пересечения моста людьми. Каждая строка стратегии содержит одно или два числа, характеризующие скорости людей, которые с фонарем пересекают мост. При существовании нескольких оптимальных стратегий пересечения реки вывести любую.