It's Senpai's turn to draw now! Senpai starts with an initially empty canvas, represented by an array of length $N$ all with $0$ layers of paint. In one brush stroke, he can add $1$ layer of paint to any subarray of length at least $L$ and at most $R$. To allow himself a wide variety of brush strokes, Senpai chooses $L$ and $R$ such that he can use at least half of all possible stroke lengths from $1$ to $N$. In the end, he aims to have exactly $A_i$ layers of paint on index $i$ for all $i$. Please tell him the minimum number of brush strokes needed to achieve this, or report that it is impossible. To ensure the integrity of your solution, there may be up to $T$ test cases.

Constraints

$1\le T\le {10}^6$

$1\le L\le R\le N\le {10}^6$

$R-L+1\ge \lceil {\displaystyle \frac{N}{2}}\rceil$

$0\le A_i\le {10}^9$

The sum of $N$ over all test cases will not exceed ${10}^6$.

Subtask 1 [20%]

$L=1,R=N$

Subtask 2 [30%]

The sum of $N$ over all test cases will not exceed $2\times {10}^3$.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer $T$, the number of test cases. The next $2T$ lines will describe the test cases.

The first line of each test case contains $3$ integers $N$, $L$, and $R$.

The second line of each test case contains $N$ integers $A_i$ $(1\le i\le N)$.

Output Specification

For each test case, output one integer on its own line: either $-1$ if it is impossible to get $A_i$ layers of paint on index $i$ for all $i$, or the minimum number of brush strokes required to accomplish the task otherwise.

Sample Input

2
5 2 4
1 2 3 4 1
5 3 5
1 2 3 4 1

Sample Output

4
-1

Explanation

One possible solution for the first test case is to use brush strokes covering the following ranges: $[1,4],[2,4],[3,4],[4,5]$.

For the second test case, it can be proven that no sequence of valid brush strokes can get $A_i$ layers of paint on index $i$ for all $i$.