The older the wine, greater its worth. Lavish and Shirin visit a wine shop eager to buy wine. Now, this unique shop has a constraint for buying wine bottles. Given, different wine bottles arranged in a line, you can only pick up a bottle from the left or the right. Both the boys take turns to pick up wine bottles and both want the best of wine for themselves. Given, that Lavish gets the first chance to pick up the wine bottles, your task is to calculate the maximum worth of wine that Lavish can possibly get by sticking to the rules of the wine shop, that is, only picking up a bottle from the left or the right and getting the maximum possible worth of wine.
Input: First line contains n, the number of wine bottles. Second line contains n space separated inputs, each describing the worth of each bottle.
Output: Maximum possible worth after picking up the bottles as per the rules.
For the first case, bottle distribution between Lavish(L) and Shirin(S) looks like :
1 2 3 4 5 6
S L S L S L
Lavish can either take the bottle with worth 1 or the one with worth 6. So, he picks up the last bottle. Now, remaining line of wine bottles looks like:
1 2 3 4 5
Out of the bottles of value 1 and 5, Shirin chooses the last one. Again Lavish chooses the bottle on the right(of worth 4). Lavish finally ends up having bottles worth 12 and Shirin worth 9
For the second case, bottle distribution among Lavish and Shirin looks like:
4 1 5 2 7
S S S L L
