408506: GYM103158 K Helping Eagle

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Helping Eagletime limit per test1 secondmemory limit per test256 megabytesinputhelp.inoutputstandard output

Your friend Eagle is playing a game.

In this game, Eagle has an array $$$A$$$ of $$$N$$$ positive integers.

In the first turn, Eagle chooses any index $$$i$$$ to start with and adds $$$A_i$$$ to his score.

Starting from the next turn, assuming that the last chosen index was index $$$i$$$. Eagle chooses any index $$$j$$$ such that $$$j$$$ wasn't chosen before and $$$|j-i| \leq 2$$$ then adds $$$A_j$$$ to his score.

Before the game starts you had a chance to choose two indices to block them such that Eagle can't choose them (at the beginning or during the game).

You would like to minimize Eagle's score if he plays optimally.

Input

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 2*10^5)$$$ the number of test cases.

Each test case consists of two lines:

First line contains one number $$$N$$$ $$$(3 \leq N \leq 2 \times 10^5)$$$ the length of the array $$$n$$$.

The second line contains $$$N$$$ integers $$$A_1, A_2 \dots A_n$$$ $$$(1 \leq A_i \leq 10^9)$$$.

The total sum of $$$N$$$ over all test cases doesn't exceed $$$2 \times 10^5$$$.

Output

For each test case, output one integer, the minimum score that Eagle gets if he plays optimally.

ExampleInput
2
5
1 1 1 1 1
3
10 15 4
Output
2
4

Source/Category

加入题单

上一题 下一题 算法标签: