Превосходство
Федерация мирового кодирования создает огромный онлайн-турнир по программированию среди команд, состоящих из пар программистов. Судья Дэвид отвечает за объединение команд из юго-восточной делегации. Каждый студент должен быть помещен в одну команду из двух учеников. К счастью, у него есть четное количество учеников, которые хотят поучаствовать в соревновании, поэтому у каждого участника есть возможность посоревноваться. Тем не менее, он хотел бы сохранить свою первозданную репутацию среди других судей, убедившись, что каждая из команд, которую он набирает для участия в соревнованиях, обладает минимальным общим рейтингом. Общий рейтинг команды определим как сумму рейтингов обоих участников в команде.
Помогите Давиду определить такое наибольшее значение X, что он сможет сформировать команды, чтобы у каждой из них общий рейтинг был не менее X.
Входные данные
Первая строка содержит натуральное число n (1 ≤ n ≤ 10^5
, n четно) - количество студентов, желающих принять участие в соревнованию по программированию. Каждая из следующих n строк содержит одно целое число s[i]
(1 ≤ s[i]
≤ 10^6
) - рейтинг студента i.
Выходные данные
Вывести наибольшее значение X такое что Давид сможет сформировать команды, каждая из которых будет иметь рейтинг больше или равный X.