Can anyone give me some hints on how to solve this type of problem? I have no clue at all...

Given an array of length N consisting of integers.(1<=N<=1000, 1<=a[i]<=100).My friend and I alternately take turns to remove either the first element or last element with probability 1/2.If a single element exists,we pick it up for sure.I have the first turn.What is the expected sum of values that I have collected?

Sample Input:


10 20

Sample Output: