There is a pawn in the lower left cell of the NxN chessboard. Two players take turns moving it, and each player can move it one space up or one space to the right. The numbers a
1, a
2, …, a
N are written on the diagonal of the board. When the pawn hits the diagonal, the game ends and the payoff of the first player is equal to the value of the number written in the square with the stopped pawn. Write a program to determine the guaranteed payoff of the first player.
Input
The first line contains the number N (1 ≤ N ≤ 100). The second line contains natural numbers a1, a2, …, aN (1 ≤ ai ≤100).
Output
Print one number – first player wins.
|
Enter |
Output |
|
8
3 1 4 1 5 9 2 6
|
5 |