AT_abc412_c [ABC412C] Giant Domino

There are $ N $ dominoes numbered from $ 1 $ to $ N $ . The size of domino $ i $ is $ S_i $ . Consider arranging some dominoes in a line from left to right and then toppling them. When domino $ i $ falls to the right, if the size of the domino placed immediately to the right of domino $ i $ is at most $ 2 S_i $ , then that domino also falls to the right. You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions: - The leftmost domino is domino $ 1 $ . - The rightmost domino is domino $ N $ . - When only domino $ 1 $ is toppled to the right, domino $ N $ eventually falls to the right as well. Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged? You are given $ T $ test cases, solve the problem for each of them.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ means the $ i $ -th test case: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ S_1 $ $ S_2 $ $ \dots $ $ S_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case. For each test case, if there is no arrangement of dominoes satisfying the conditions, output `-1`; otherwise, output the minimum number of dominoes to arrange.

### Sample Explanation 1 For the $ 1 $ st test case, arranging the dominoes from left to right in the order domino $ 1 $ , domino $ 3 $ , domino $ 2 $ , domino $ 4 $ satisfies the conditions in the problem statement. Specifically, for the $ 3 $ rd condition, when only domino $ 1 $ is toppled to the right, the dominoes fall in the following order: - Domino $ 3 $ is placed to the right of domino $ 1 $ . Since the size of domino $ 3 $ , $ S_3 = 2 $ , is not greater than $ S_1 \times 2 = 1 \times 2 = 2 $ , domino $ 3 $ also falls to the right. - Domino $ 2 $ is placed to the right of domino $ 3 $ . Since the size of domino $ 2 $ , $ S_2 = 3 $ , is not greater than $ S_3 \times 2 = 2 \times 2 = 4 $ , domino $ 2 $ also falls to the right. - Domino $ 4 $ is placed to the right of domino $ 2 $ . Since the size of domino $ 4 $ , $ S_4 = 5 $ , is not greater than $ S_2 \times 2 = 3 \times 2 = 6 $ , domino $ 4 $ also falls to the right. It is impossible to achieve the conditions in the problem statement by arranging $ 3 $ or fewer dominoes, so the answer is $ 4 $ . ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq S_i \leq 10^9 $ - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.