Two players A and B are playing a game optimally. There is an array of N integers. Player A starts the game. In each move any player can pick any number of numbers (minimum 2 numbers must be selected) from the prefix of the array and add it to his own score. The player removes the selected numbers from the prefix of array and the sum of the removed numbers is appended at the prefix of the array. The game ends when there is one number left in array. Return the maximum difference in score of A and B

Example:

If the game with array [1,2,3,4] and player selects first 4 numbers then succeding array for other players move will be [10] and game would end as 2nd player wouldn't be able to pick 2 numbers from array. Therefore player 1 has score of 10 and player 2 has score of 0. Thus answer would be 10

Constraints

• 1 <= lengthOfArray <= 105
• -1000 <= arr[i] <=1000

Test Cases:

• Input: arr = [1]
  Output: 0

• Input: arr = [1,2,3,4,5]
  Output: 15

• Input: arr = [-2,-5,-4,2,1]
  Output: -1

• Input: arr = [5,10,-2,1,-900,15,-3]
  Output: 11

• Input: arr = [5,10,-2,15]
  Output: 28

• Input: arr = [-2,-5,-4,-10,-100,100]
  Output: 0