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

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

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

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

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

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