ACPC11C - Circleland

no tags 

 

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.

 

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_: 2018-06-22 18:15:16

Prefix sum and 4 conditions :)

yvasant: 2017-12-12 16:16:51

AC in one go :)

Utkarsh Rastogi: 2014-11-03 10:41:28

Not initializing array to 0 in every testcase costed me 3 WA...
Finally AC.. :)

Seshadri R: 2014-10-28 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:
7 100 15 20 42 33 15 24
be 149?

Sunny: 2014-05-14 09:41:58

@Francis : what are the answers of your given test cases ..?

Francis: 2014-05-12 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 re-enter.". That indeed confuses me a lot at first.
(2)"You can walk in both directions in every corridor." means "Same room can be visited twice".
(3)useful test cases
4
6 5 7 8 10 9 1
6 1 2 3 1000 4 1
5 1 1000 2 1001 3
6 1 4 1000 2 1001 3


@Sunny Jain
32
16
1008
1013

Last edit: 2014-05-14 13:24:41
Amit : 2013-06-26 16:10:04

@divya gupta: test case for u !!!
1
6 5 7 8 10 9 1
ans is 32 !!!

Last edit: 2013-06-26 16:16:58
divya gupta: 2013-06-13 08:46:16

plz check http://ideone.com/PZM4hC

divya gupta: 2013-06-13 08:19:43

anyone please check my solution..
tired of debugging..


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