CF1995C.Squaring

ikrpprpp 找到了一组由整数构成的数组 $a$。他热爱正义，因此他希望让 $a$ 变得“公平”——也就是让它变为非递减数组。为此，他可以对数组中 $1 \le i \le n$ 的某个下标执行一次“正义之举”，即将 $a_i$ 替换为 $a_i^2$（即将第 $i$ 个元素替换为它的平方）。例如，如果 $a = [2,4,3,3,5,3]$，ikrpprpp 选择对 $i = 4$ 执行一次正义之举后，$a$ 变为 $[2,4,3,9,5,3]$。

请你求出最少需要多少次正义之举，才能使数组 $a$ 变为非递减数组。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是每个测试用例的描述。

对于每个测试用例，第一行包含一个整数 $n$，表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示使数组 $a$ 变为非递减数组所需的最少正义之举次数。如果无法做到，输出 $-1$。

在第一个测试用例中，不需要执行任何正义之举，数组本身就是公平的！

在第三个测试用例中，可以证明无法将数组变为非递减数组。

在第五个测试用例中，ikrpprppp 可以先对下标 3 执行一次正义之举，再对下标 2 执行一次，最后再对下标 3 执行一次。此后，$a$ 将变为 $[4, 9, 16]$。

由 ChatGPT 4.1 翻译