Очень скоро сдача проекта, а ещё ничего не готово! Компании нужно срочно распланировать, кто и чем будет заниматься, чтобы всё успеть.
Всего в компании работает 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.
