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

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

Вхідні дані

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

Вихідні дані

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