ACPC11C  Circleland
You are visiting circleland, and you have long waited to visit their famous art exhibition. The exhibition has N rooms arranged in a cycle. In every room, there are some artistic pieces. The rooms are named R1 , R2 , ..., RN . There are also N corridors, named C1 , C2 , ..., CN , of lengths L1 , L2 , ..., LN , respectively. Each corridor Ci connects the two rooms Ri and Ri+1 , except CN which connects RN and R1 . Thus, the whole exhibition forms a cycle. You can walk in both directions in every corridor.
There is a single entrance to the exhibition in room R1 , but there are exits in every room. As there is nothing interesting to see in the corridors, you would like to spend the least effort walking through corridors in the exhibition. Compute the minimum total distance you need to walk in corridors such that you enter from the entrance, exit from any exit and visit all rooms.
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T , the number of test cases (1 ≤ T ≤ 100). Next T lines contain the test cases, each on a single line.
Each case starts with an integer N , the number of rooms in the exhibition (2 ≤ N ≤ 100, 000), followed by N numbers, the lengths of the corridors, L1 , L2 , ..., LN , in this order (1 ≤ Li ≤ 1,000,000).
The sum of the lengths of all corridors will not exceed 1,000,000,000.
Output
For each test case, output, on a single line, a single number representing the minimum total distance you have to walk in corridors such that you visit all rooms.
Example
Input: 2 5 1 1 1 1 1 7 100 15 20 42 33 15 24 Output: 4 149
hide comments
mag1x_:
20180622 18:15:16
Prefix sum and 4 conditions :) 

yvasant:
20171212 16:16:51
AC in one go :)


Utkarsh Rastogi:
20141103 10:41:28
Not initializing array to 0 in every testcase costed me 3 WA...


Seshadri R:
20141028 09:32:42
I suppose that you can enter either from R1 or from RN. Otherwise, how the result for the following example test case:


Sunny:
20140514 09:41:58
@Francis : what are the answers of your given test cases ..? 

Francis:
20140512 13:58:13
(1)"exit from any exit and visit all rooms." should be "visit all rooms and exit from any exit.", which is equal to "You're not allowed to exit and reenter.". That indeed confuses me a lot at first.


Amit :
20130626 16:10:04
@divya gupta: test case for u !!!


divya gupta:
20130613 08:46:16
plz check http://ideone.com/PZM4hC 

divya gupta:
20130613 08:19:43
anyone please check my solution..

Added by:  mohamedwahba 
Date:  20111215 
Time limit:  2.441s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Arab Collegiate Programming Contest 2011 