该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

育华多米诺

题目描述

育华学校开展多米诺骨牌趣味挑战活动，准备了 $N$ 个特制多米诺骨牌，编号从 $1$ 到 $N$。每个多米诺骨牌 $i$ 有对应的尺寸 $S_i$ 。

活动规则是挑选两个或更多多米诺骨牌，按从左到右顺序排列好，要满足这些条件：

1. 最左边摆放的必须是编号为 $1$ 的多米诺骨牌（象征活动起点 ）。
2. 最右边摆放的必须是编号为 $N$ 的多米诺骨牌（象征活动终点 ）。
3. 当推倒最左边的编号为 $1$ 的多米诺骨牌让它向右倒时，最右边编号为 $N$ 的多米诺骨牌最终也得跟着向右倒。

多米诺骨牌倒下传递规则：当多米诺骨牌 $i$ 向右倒时，要是紧挨着它右边的多米诺骨牌 $j$ 尺寸满足 $S_j \leq 2 \times S_i$ ，那骨牌 $j$ 会被带动也向右倒。

现在要判断对于每组骨牌，是否存在符合条件的排列方式。若存在，算出需要排列的多米诺骨牌的最少数量；若不存在，就输出 -1 。本次挑战有 $T$ 组不同的骨牌配置，得逐个处理求解。

输入格式

输入从标准输入按如下格式给出，其中 case_i 代表第 $i$ 组挑战用例：

T  
case_1  
case_2  
...  
case_T  

每组挑战用例的格式是：

N  
S_1 S_2 ... S_N  

输出格式

输出 $T$ 行，第 $i$ 行对应第 $i$ 组挑战用例的结果：

• 要是存在符合条件的排列，输出所需多米诺骨牌的最少数量；
• 若不存在，输出 -1 。

样例说明（以样例输入 1 为例）

样例输入 1

3  
4  
1 3 2 5  
2  
1 100  
10  
298077099 76263489 44093234 59197620 725560241 589990757 965885936 633331126 589925214 978729735  

样例输出 1

4  
-1  
3  

样例 2

见选手文件中的 domino/domino2.in 与 domino/domino2.ans。

解释（第一组挑战用例）

把多米诺骨牌按 1 → 3 → 2 → 4 的顺序排列，能满足所有要求：

1. 最右边是编号 $4$（对应规则里“最左侧是 $N$”，这里 $N = 4$ ）。
2. 最左边是编号 $1$ 。
3. 推倒最左边的 $1$ 时：
   • $1$ 右边是 $3$ ，因为 $S_3 = 2 \leq 2 \times S_1 = 2 \times 1 = 2$ ，所以 $3$ 会被带倒。
   • $3$ 右边是 $2$ ，因为 $S_2 = 3 \leq 2 \times S_3 = 2 \times 2 = 4$ ，所以 $2$ 会被带倒。
   • $2$ 右边是 $4$ ，因为 $S_4 = 5 \leq 2 \times S_2 = 2 \times 3 = 6$ ，所以 $4$ 会被带倒。

要是尝试用 3 个或更少骨牌排列，没法满足条件。所以，最少需要 4 个骨牌。

数据规模