Максим та останнє випробування
Обмеження: 2 сек., 256 МіБ
«Скільки всього я пройшов...» — думав Максим, згадуючи свої останні пригоди. Веселі гулянки в улюбленому місті, заснованому в 1708 році, до роздачі цукерок дівчатам. А тепер він на самому верху замку дракона.
Зібравшись із силами він відчинив двері та не зміг повірити своїм очам. Принцеса сиділа на кріслі, ніби чекала його, ціла та неушкоджена.
«Це все були випробування, щоб перевірити, чи можеш ти поєднувати в житті своє місто та його принцесу», — сказала дівчина. Максим не міг нічого сказати, але розумів, що прийшов час останнього завдання, і він не може з ним не справитися.
Принцеса передала йому набір з n карток (n непарне). На кожній картці було написане якесь унікальне ціле число.
На кожному кроці, поки кількість карток не менша за три, Максим може вибрати 3 довільних картки, викинути ті, що мають максимальне та мінімальне значення, а середню покласти назад до набору.
Щоб пройти останнє завдання успішно, хлопець повинен сказати, яке максимальне число можна отримати на останній картці, якщо діяти оптимально.
Вхідні дані
У першому рядку задано ціле число n — розмір набору.
У другому рядку задано n різних цілих чисел ai — значення на кожній картці.
Вихідні дані
В одному рядку виведіть ціле число — максимальне значення, що може отримати Максим на останній картці.
Обмеження
1≤n≤105,
n непарне,
|ai|≤1018.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 5 1 2 -4 3 7 | 3 |