eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Превосходство

Превосходство

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Федерация мирового кодирования создает огромный онлайн-турнир по программированию среди команд, состоящих из пар программистов. Судья Дэвид отвечает за объединение команд из юго-восточной делегации. Каждый студент должен быть помещен в одну команду из двух учеников. К счастью, у него есть четное количество учеников, которые хотят поучаствовать в соревновании, поэтому у каждого участника есть возможность посоревноваться. Тем не менее, он хотел бы сохранить свою первозданную репутацию среди других судей, убедившись, что каждая из команд, которую он набирает для участия в соревнованиях, обладает минимальным общим рейтингом. Общий рейтинг команды определим как сумму рейтингов обоих участников в команде.

Помогите Давиду определить такое наибольшее значение X, что он сможет сформировать команды, чтобы у каждой из них общий рейтинг был не менее X.

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

Первая строка содержит натуральное число n (1n10^5, n четно) - количество студентов, желающих принять участие в соревнованию по программированию. Каждая из следующих n строк содержит одно целое число s[i] (1s[i]10^6) - рейтинг студента i.

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

Вывести наибольшее значение X такое что Давид сможет сформировать команды, каждая из которых будет иметь рейтинг больше или равный X.

Пример

Входные данные #1
4
1
2
3
5
Выходные данные #1
5
Источник 2015 ACM North America - Pacific Northwest, Дивизион 1, Задача E