Max Collectable Score

You are given a sequence of scores. Two players, Alice and Bob, collect scores by choosing values from either end of the list. At each step, the player picks the end (either left or right) with the higher score. Your task is to determine the maximum score that either player collects during the process.

Formally, let the array of scores be \(a_1,a_2,\dots,a_N\). Two pointers are maintained: one at the beginning and one at the end of the array. In each move, if \(a_{left} > a_{right}\) then the score from the left end is considered, otherwise the score from the right end is chosen. The maximum score encountered during all moves is the answer.

Note: It is guaranteed that the list contains at least one element.

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\)) representing the number of scores.

The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\) where \(0 \le a_i \le 10^9\).

outputFormat

Output a single integer: the maximum score collected by either player.

5
1 2 9 2 1

9