9559번 - 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 R₁, R₂, ..., R_N . There are also N corridors, named C₁, C₂, ..., C_N , of lengths L₁, L₂, ..., L_N , respectively. Each corridor Ci connects the two rooms R_i and R_i+1, except C_N which connects R_N and R₁. 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 R₁, 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.

입력

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, L₁, L₂, ..., L_N , in this order (1 ≤ L_i ≤ 1, 000, 000).

The sum of the lengths of all corridors will not exceed 1, 000, 000, 000.

출력

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.

제한

힌트