G. Распределение работ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень скоро сдача проекта, а ещё ничего не готово! Компании нужно срочно распланировать, кто и чем будет заниматься, чтобы всё успеть.

Всего в компании работает n человек, причём n — чётное положительное число. Они работают в парах: первый со вторым, третий с четвёртым, ..., (n - 1)-й с n-м. Проект, над которым работает компания, также состоит из n частей, при этом сложность i-й части равна ai.

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

Работник, выполняя свою часть проекта в очередной день, испытывает стресс, если сложность работы его напарника в этот день меньше, чем у него самого. При этом величиной стресса будем считать модуль разности между сложностями частей проекта. Например, если пятый сотрудник выполняет часть проекта со сложностью 10, а шестой сотрудник — со сложностью 15, то величина стресса пятого сотрудника будет равна 0, а величина стресса шестого сотрудника будет равна |10 - 15| = 5.

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

Составьте оптимальное распределение работы на n дней, которое минимизирует суммарный стресс сотрудников.

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

В первой строке следует целое число n (2 ≤ n ≤ 150) — количество работников, количество частей проекта и количество дней до срока сдачи. Гарантируется, что n — чётное число.

Во второй строке следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 5 000), где ai равно сложности i-й части проекта.

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

В первую строку выведите минимально возможный суммарный стресс, который могут получить сотрудники компании.

В каждую из следующих n строк выведите по n целых чисел, при этом j-е число в i-й строке должно быть равно номеру части проекта, над которой должен работать j-й сотрудник в i-й день в оптимальном распределении.

Примеры
Входные данные
2
3 1
Выходные данные
4
1 2
2 1
Входные данные
4
2 2 2 3
Выходные данные
4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
Входные данные
4
4 4 7 1
Выходные данные
24
1 4 2 3
3 1 4 2
2 3 1 4
4 2 3 1
Примечание

Посчитаем для каждого примера суммарный стресс, полученный работниками.

В первом тесте:

(|a1 - a2| + 0) + 

(0 + |a2 - a1|) = 2 + 2 = 4.

Во втором тесте:

(0 + 0 + 0 + |a4 - a3|) + 

(0 + 0 + |a4 - a1| + 0) + 

(0 + |a4 - a3| + 0 + 0) + 

(|a4 - a1| + 0 + 0 + 0) = 1 + 1 + 1 + 1 = 4.

В третьем тесте:

(|a1 - a4| + 0 + 0 + |a3 - a2|) + 

(|a3 - a1| + 0 + 0 + |a2 - a4|) + 

(0 + |a3 - a2| + |a1 - a4| + 0) + 

(0 + |a2 - a4| + |a3 - a1| + 0) = 24.