DCEPC301  Foodie Golu
Being a big foodie Golu wants to try all the dishes available at a party but because of his increasing weight his mother does not allow him to do so. After a huge fight they both come to an agreement.
1. The first rule of the agreement says that Golu should only eat at an interval of 10 minutes.
2. The second rule is regarding the stalls available. There are N stalls in one line and Golu should select only one stall to eat at one time. The selected stall must lie at the n/2th position or (n/2 + 1) position (zero indexed) among all remaining stalls.
3. Once he has selected a stall he must discard all the stalls to its left (or right) and in future can only eat from the remaining stalls. Also he can eat from a stall only once during the party, so once he has eaten from a stall, it should be discarded too.
The initial cooking speed at all the stalls is 1 unit. After doing some calculations Golu realises that the speed of cooking of the cook at every stall becomes double every 10 minutes. Depending upon the type of dish available and his eating capacity, he assigned a value to each stall such that any point of time he can eat a quantity which is equal to (value of that stall) * (current speed of cooking at that stall). Since speed is increasing exponentially he only remembers speed as speed % mod at any time.
Since he wants to eat the maximum amount of food, help him in developing a strategy to eat.
NOTE: If there are only 2 stalls left, he must choose any one stall and discard the other.
Input
First line contains T, the number of test cases. (1<=T<=5)
First line of each test case contains n, the number of stalls in the party. (1<=n<=3000)
Next line of each test case contains n space separated integers, representing the value of each of the stalls. (All values are between 1 and 3000 inclusive)
Output
Output T lines, one for each test case containing the maximum amount of food Golu can eat mod 10^9+7
Example
Input:1
5
2 4 1 3 5
Output: 21
Explanation:
Golu can select the fourth stall first and discard all stalls to its right (i.e discard fifth stall). Then he can select the third stall and again discard all stalls to its right (no stall to discard this time). Finally he chooses the 2^{nd} stall.Therefore total food he can eat = 3*1 + 1*2 + 4*4 = 21.
hide comments
Aman Gupta:
20121112 23:18:57
Are we supposed to maximize food eaten or food eaten mod 10^9 + 7?


ketul shah:
20120628 10:54:26
can anybody give large test case and also its answer 

Sidharth Gupta:
20120517 13:18:05
@Prateek: speed = (2*speed)%mod. 

Prateek Sultania:
20120512 15:27:12
Since speed is increasing exponentially he only remembers speed as speed % mod at any time.


RAJDEEP GUPTA:
20120427 19:23:26
what is the answer for

Added by:  dce coders 
Date:  20120306 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 