Given an array A of N numbers, and an initially empty array P, you can do operations of 4 types on it:
Note that after each operation, array A becomes smaller and maybe reversed. You need to continue adding elements to array P until the array A has 0 elements. You need to maximise the sum of all the values in array P.
Input:
First line contains a single integer N. Next line contains N space separated integers denoting the array A.
Output:
Output the maximum sum of all elements of array P that can be obtained by doing the 4 operations as described above on the array A.
Constraints:
We can get by doing the operations in this order: .
After first operation () :
After second operation () :
After third operation () :
Total sum at the end is .