Задача H. Перед экзаменом
Задачу добавил: alef
Успешно сдано решений: 30
Преподаватели тоже готовятся к экзаменам. Так, в частности, важно сформировать билеты таким образом, чтобы они не слишком отличались друг от друга по сложности.
У преподавателя имеется 2N теоретических вопросов, сложность которых он оценивает целыми положительными числами A[1], A[2], ...., A[2N].
Билет состоит из двух теоретических вопросов. Преподаватель хочет сформировать N билетов таким образом, чтобы каждый теоретический вопрос встречался в билетах ровно один раз. При этом он хочет, чтобы билеты отличались друг от друга по сложности как можно меньше. Ваша задача — найти такой вариант формирования билетов, при котором самый сложный билет отличается от самого простого на минимально возможную величину. Сложность билета определяется суммой сложностей составляющих его вопросов.
Формат входного файла input.txt
Первая строка — целое число N (1 <= N <= 10^5), описанное в условии задачи
Вторая строка — 2N целых чисел A[1], A[2], ..., A[2N] — сложности вопросов (все числа натуральные и не превосходят 10^8)
Формат выходного файла output.txt
Первая строка — целое число, разность между сложностью самого сложного билета и самого простого.
Каждая из следующих N строк является описанием билета. Описание билета состоит из номера первого вопроса и номера второго вопроса, записанных через пробел.
Пример входного файла
3
3 2 9 2 7 2
Пример выходного файла
6
3 2
1 4
5 6