← 返回题目列表

AtCoder · abc412_c

E. 巨型多米诺骨牌

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 多米诺骨牌编号为 1 to N。多米诺骨牌的大小 i is S_i.
考虑将一些多米诺骨牌从左到右排成一行,然后将它们推倒。当多米诺骨牌 i 落在右侧,如果多米诺骨牌的大小立即放置在多米诺骨牌的右侧 i 最多是 2 S_i,那么那张多米诺骨牌也向右倒下。

您决定选择两个或多个多米诺骨牌并将它们从左到右排成一行。多米诺骨牌的排列必须满足以下条件:

  • 最左边的多米诺骨牌是多米诺骨牌 1.
  • 最右边的多米诺骨牌是多米诺骨牌 N.
  • 当只有多米诺骨牌时 1 向右倒塌,多米诺骨牌 N 最终也落到了右边。

满足条件的多米诺骨牌排列是否存在?如果存在,最少需要排列多少张多米诺骨牌?

你被给予 T 测试用例,解决每个用例的问题。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
S_1 S_2 \dots S_N

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,如果没有满足条件的多米诺骨牌排列,则输出 -1;否则,输出要排列的最少多米诺骨牌数量。


示例输入 1

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

示例输出 1

4
-1
3

对于 1st 测试用例,按照多米诺骨牌顺序从左到右排列多米诺骨牌 1,多米诺骨牌 3,多米诺骨牌 2,多米诺骨牌 4 满足问题陈述中的条件。具体来说,对于 3rd 条件,仅当多米诺骨牌时 1 向右倒下,多米诺骨牌按以下顺序倒下:

  • 多米诺骨牌 3 被放置在多米诺骨牌的右侧 1。由于多米诺骨牌的大小 3, S_3 = 2,不大于 S_1 \times 2 = 1 \times 2 = 2,多米诺骨牌 3 也落在右侧。
  • 多米诺骨牌 2 被放置在多米诺骨牌的右侧 3。由于多米诺骨牌的大小 2, S_2 = 3,不大于 S_3 \times 2 = 2 \times 2 = 4,多米诺骨牌 2 也落在右侧。
  • 多米诺骨牌 4 被放置在多米诺骨牌的右侧 2。由于多米诺骨牌的大小 4, S_4 = 5,不大于 S_2 \times 2 = 3 \times 2 = 6,多米诺骨牌 4 也落在右侧。

通过排列不可能实现问题陈述中的条件 3 或更少的多米诺骨牌,所以答案是 4.