CF1490A Dense Array

Polycarp 称一个数组为稠密的，如果任意两个相邻元素中较大的那个不超过较小的两倍。更正式地，对于任意 $i$（$1 \le i \le n-1$），必须满足以下条件：$\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2$。 例如，数组 $[1, 2, 3, 4, 3]$、$[1, 1, 1]$ 和 $[5, 10]$ 是稠密的。而数组 $[5, 11]$、$[1, 4, 2]$、$[6, 6, 1]$ 不是稠密的。 现在给定一个长度为 $n$ 的整数数组 $a$。你需要求出最少需要在数组中插入多少个数，使其变为稠密的？你可以在数组的任意位置插入数字。如果数组本身已经是稠密的，则不需要插入任何数字。 例如，如果 $a=[4,2,10,1]$，那么答案是 $5$，插入元素后的数组可能为： $a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]$（当然还有其他构造方式）。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 接下来每个测试用例包含两行。 第一行包含一个整数 $n$（$2 \le n \le 50$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 50$）。

对于每个测试用例，输出一个整数，表示最少需要插入多少个数才能使数组变为稠密。

第一个测试用例的解释见题面。 第二个测试用例，你可以插入一个元素，$a=[1,\underline{\textbf{2}},3]$。 第三个测试用例，你可以插入两个元素，$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$。 第四个测试用例，你可以插入一个元素，$a=[1,\underline{\textbf{2}},4,2]$。 第五个测试用例，数组 $a$ 已经是稠密的。 由 ChatGPT 4.1 翻译