Вам дан массив \(a\) из \(n\) целых чисел, где \(n\) — нечётное.
За одну операцию вы можете удалить из массива \(a\) два соседних элемента, а затем объединить оставшиеся части массива. Например, из массива \([4,7,4,2,9]\) можно получить массивы \([4,2,9]\) и \([4,7,9]\) с помощью операций \([\underline{4,7}, 4,2,9] \to [4,2,9]\) и \([4,7,\underline{4,2},9] \to [4,7,9]\) соответственно. Однако мы не можем получить массив \([7,2,9]\), так как для этого нужно удалить несмежные элементы \([\underline{4},7,\underline{4},2,9]\).
Вы выполняете эту операцию несколько раз, пока в \(a\) не останется ровно один элемент.
Найдите максимально возможное значение оставшегося элемента в \(a\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное значение оставшегося элемента в \(a\).
Примечание
В первом наборе входных данных массив \(a\) равен \([6]\). Поскольку в нем только один элемент, никаких операций не требуется. Максимально возможное значение оставшегося элемента — \(6\).
Во втором наборе входных данных массив \(a\) равен \([1, 3, 2]\). Мы можем удалить первые два элемента \([\underline{1, 3}, 2] \to [2]\), или удалить последние два элемента \([1, \underline{3, 2}] \to [1]\). Таким образом, максимально возможное значение оставшегося элемента равно \(2\).
В третьем наборе входных данных массив \(a\) равен \([4, 7, 4, 2, 9]\). Один из способов максимизации оставшегося элемента — \([4, \underline{7, 4}, 2, 9] \to [\underline{4, 2}, 9] \to [9]\). Таким образом, максимально возможное значение оставшегося элемента равно \(9\).
В четвертом наборе входных данных массив \(a\) равен \([3, 1, 4, 1, 5, 9, 2]\). Можно показать, что максимально возможное значение оставшегося элемента равно \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
6
3
1 3 2
5
4 7 4 2 9
7
3 1 4 1 5 9 2
|
6
2
9
5
|