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

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

hide comments
2013-05-21 07:33:10 Akb
got AC in 0.09...second fastest solution as of now...!! :)
2013-05-21 07:33:10 divya gupta
@admin...please check my solution id 9104065
i considered all the cases ..

Last edit: 2013-04-15 15:25:00
2013-05-21 07:33:10 Devil D
Correct answer for
1
6 1 2 3 1000 4 1

is 16
2013-05-21 07:33:10 I_AM
@laplace: answer should be 16...
@smit : Yes, Same room can be visited twice..

Last edit: 2012-03-16 09:54:50
2013-05-21 07:33:10 ! include(L.ppt)
@laplace : answer for ur test case is 16 acc. to me........

Last edit: 2012-01-31 13:17:39
2013-05-21 07:33:10 Laplace
wah AC :)
Check your answer for
1
6 1 2 3 1000 4 1
2013-05-21 07:33:10 Smit Mehta
can he visit the same room twice?
2013-05-21 07:33:10 Devil D
@mitch - thanks for the hint .
i was assuming multiple entry
2013-05-21 07:33:10 neerajcrespo
altogether, there can be only four possible cases. is there any tricky case? WA :(
ID: 6244391

Last edit: 2011-12-26 07:37:28
2013-05-21 07:33:10 Aniket Divekar
plz give some more test cases(tricky if possible)
thanku
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.