408506: GYM103158 K Helping Eagle

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.

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$$$.

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

2
5
1 1 1 1 1
3
10 15 4

2
4