核心思路

操作只能使元素变大（因为 $x \ge 1$ 时 $x^2 \ge x$），因此要满足 $a_{i-1} \le a_i$：

• 如果当前 $a_{i-1} > a_i$，我们必须对 $a_i$ 进行若干次平方操作，使其不小于 $a_{i-1}$。
• 注意，对 $a_{i-1}$ 进行平方操作会使其变得更大，只会恶化前面已经满足的不等式，因此我们只对后面的元素进行操作，不会回头操作前面的元素。
• 另外，如果某个 $a_i = 1$，则 $1^2 = 1$，操作无效；如果 $a_{i-1} > 1$ 且 $a_i = 1$，则永远无法使 $a_{i-1} \le a_i$，因为 $1$ 的平方永远是 $1$，而 $a_{i-1} > 1$ 且不会变小，此时答案为 $-1$。

于是可以从左到右贪心：维护当前位置经过若干次平方后的值（实际维护的是其对数，避免数值爆炸），对于每个 $i$（$2 \le i \le n$），计算需要多少次平方才能使 $a_i$ 不小于 $a_{i-1}$。

数值爆炸问题

直接计算平方会导致数字巨大（例如 $2^{2^{20}}$ 远超计算机能表示的范围），但操作次数并不会很大。注意到：

• 当 $x \ge 2$ 时，平方一次后至少为 $4$，再平方一次至少为 $16$，增长极快。实际上，从 $2$ 开始，平方 $k$ 次后变为 $2^{2^k}$。
• 我们最多需要对一个元素操作多少次？因为 $a_i \le 10^6$，而 $a_{i-1}$ 在经过前面操作后可能变得很大（但本身也是通过平方得到的）。实际上，如果 $a_{i-1}$ 已经很大，那么 $a_i$ 只需要少量平方就能超过它；如果 $a_{i-1}$ 比较小，那么 $a_i$ 需要的平方次数也很有限。

为了安全且高效地计算，我们使用双对数（$\log \log$）技巧。

双对数变换

定义： [ b_i = \log(\log(a_i)) ] 其中 $\log$ 通常取自然对数或 $\log_2$，只要底数一致即可。本题中采用 $\log_2$ 会非常方便，因为平方操作对应： [ \log_2(x^2) = 2\log_2(x) ] 再取一次对数： [ \log_2(\log_2(x^2)) = \log_2(2\log_2(x)) = \log_2(2) + \log_2(\log_2(x)) = 1 + \log_2(\log_2(x)) ] 也就是说，在双对数空间（底数为 $2$）中，一次平方操作等价于加 $1$！

这样我们就不再需要处理巨大的数值，只需要在 $b_i$ 上加一个常数即可。由于 $a_i \le 10^6$，$\log_2(10^6) \approx 20$，所以 $\log_2(\log_2(10^6)) \approx \log_2(20) \approx 4.32$，范围非常小。即使经过很多次操作，$b_i$ 也只会线性增长（最多加 $n$ 次），完全在浮点数的精度范围内。

贪心过程

初始化 $b_i = \log_2(\log_2(a_i))$，同时维护当前答案 $ans = 0$。
对于 $i$ 从 $2$ 到 $n$：

1. 若 $a_{i-1} = 1$：此时 $b_{i-1}$ 无定义（$\log(1)=0$，再取 $\log$ 为 $-\infty$）。需单独处理：

   • 如果 $a_{i-1} = 1$ 且 $a_i = 1$，则已经满足，不需要操作。
   • 如果 $a_{i-1} = 1$ 且 $a_i > 1$，那么无论对 $a_i$ 做多少次平方，$a_i$ 始终 $\ge 2$，而 $a_{i-1}$ 永远为 $1$，所以不等式自动满足，不需要操作。
   • 如果 $a_{i-1} > 1$ 且 $a_i = 1$，则永远无法使 $1$ 变大，直接输出 $-1$。

2. 一般情况 $a_{i-1} > 1$ 且 $a_i > 1$：

   • 我们要找到最小的非负整数 $k$，使得对 $a_i$ 进行 $k$ 次平方后，满足 $a_i^{2^k} \ge a_{i-1}$。
   • 在双对数空间，$a_i$ 平方 $k$ 次后的双对数值为 $b_i + k$（因为每次加 $1$）。而 $a_{i-1}$ 的双对数值为 $b_{i-1}$。不等式等价于： [ b_i + k \ge b_{i-1} ] 因此 $k = \lceil b_{i-1} - b_i \rceil$，但需要保证 $k \ge 0$。
   • 注意，由于 $a_{i-1}$ 本身可能已经被前面的操作修改过（实际上我们并不真正修改 $a_{i-1}$，而是在双对数空间维护它的值），但 $b_{i-1}$ 已经反映了它经过若干次平方后的状态。因此 $b_{i-1}$ 是我们当前维护的值，而 $b_i$ 是原始值。我们需要将 $b_i$ 更新为 $b_i + k$（因为对 $a_i$ 执行了 $k$ 次平方）。
   • 将 $k$ 累加到答案 $ans$ 中。

3. 特殊情况：当 $a_i = 1$ 但 $a_{i-1} > 1$ 已经在第一步判断为不可能。如果 $a_{i-1}=1$ 且 $a_i=1$，则 $b_{i-1}$ 和 $b_i$ 都无法定义，但我们已经知道不需要操作，直接跳过。

4. 关于精度：由于 $b_i$ 是浮点数，直接计算 $\lceil b_{i-1} - b_i \rceil$ 可能因浮点误差产生 $1$ 的偏差。可以在计算时加一个极小量（如 $10^{-12}$）再取整，或者使用整数方法（见下文）。

整数方法（替代浮点）

如果不希望使用浮点数，也可以用整数记录“对数”或直接利用指数比较。由于操作次数很小，我们可以直接模拟平方，但需要防止溢出。一个常用技巧是：当 $a_i$ 已经大于某个阈值（比如 $10^9$）时，它的平方会爆炸，但此时它显然已经大于任何可能的前驱，所以我们可以设定一个上限，比如一旦 $a_i > 10^6$ 且 $a_i$ 远大于 $a_{i-1}$，就不再继续平方。不过这种方法实现起来稍复杂，浮点双对数方法更简洁安全。

算法步骤总结

1. 读入 $t$，对每个测试用例：
   • 读入 $n$ 和数组 $a$。
   • 预处理：如果出现 $a_{i-1} > 1$ 且 $a_i = 1$，直接输出 $-1$ 并跳过。
   • 计算 $b_i = \log_2(\log_2(a_i))$，注意当 $a_i = 1$ 时，我们将其双对数视为 $-\infty$，但在代码中可以用一个特殊标记（例如 -1e18）表示，并在比较时单独处理。
   • 初始化 $ans = 0$。
   • 从 $i = 2$ 到 $n$：
     • 如果 $a_{i-1} = 1$，则无需操作（$a_i$ 自动满足 $\ge 1$），且 $b_{i-1}$ 为负无穷，跳过。
     • 否则：
       • 计算 $k = \lceil b_{i-1} - b_i \rceil$，如果 $k < 0$ 则 $k = 0$。
       • $ans \leftarrow ans + k$。
       • 更新 $b_i \leftarrow b_i + k$。
   • 输出 $ans$。

复杂度分析

• 每个测试用例 $O(n)$ 时间。
• 浮点运算精度足够，且 $n$ 总和不超过 $2\times 10^5$，完全可行。

示例验证

以第五个例子为例：$a = [4,3,2]$。

• $b_1 = \log_2(\log_2 4) = \log_2(2) = 1$。
• $b_2 = \log_2(\log_2 3) \approx \log_2(1.585) \approx 0.664$。
• $i=2$：$k = \lceil 1 - 0.664 \rceil = 1$，$ans=1$，更新 $b_2 = 0.664+1=1.664$。
• $i=3$：$b_3 = \log_2(\log_2 2) = \log_2(1)=0$。
• $k = \lceil 1.664 - 0 \rceil = 2$，$ans=3$，更新 $b_3 = 0+2=2$。 最终答案 $3$，与样例一致。

参考代码

#include <bits/stdc++.h>
using namespace std;

const double INF = 1e18;  // 用于表示 log(log(1)) = -∞
const double EPS = 1e-12;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 特殊情况：若存在 a[i]==1 且 a[i-1]>1，永远无法使 a[i-1] <= a[i]
    for (int i = 1; i < n; ++i) {
        if (a[i] == 1 && a[i-1] > 1) {
            cout << "-1\n";
            return;
        }
    }

    // 计算每个元素的双对数 b[i] = log2(log2(a[i]))
    vector<double> b(n);
    for (int i = 0; i < n; ++i) {
        if (a[i] == 1)
            b[i] = -INF;          // log2(log2(1)) 无定义，用负无穷表示
        else
            b[i] = log2(log2(a[i]));
    }

    long long ans = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i-1] == 1) {
            // 前一个数是 1，不等式自动成立，不需要操作
            continue;
        }
        // 此时 a[i-1] > 1 且 a[i] > 1（因为前面已经排除了 a[i]==1 的情况）
        double diff = b[i-1] - b[i];
        long long k = 0;
        if (diff > EPS) {
            // 需要 ceil(diff) 次操作，注意浮点误差
            k = (long long)ceil(diff - EPS);
        }
        ans += k;
        b[i] += k;   // 更新 b[i] 为操作后的值
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

注意事项

• 当 $a_i = 1$ 且 $a_{i-1} > 1$ 时无解，因为 $1$ 的任何次方都是 $1$，无法变大。
• 当 $a_{i-1} = 1$ 且 $a_i = 1$ 时，虽然双对数无定义，但不等式自动满足。
• 浮点误差处理：计算 $k = \max(0, \lceil b_{i-1} - b_i - 1e-12 \rceil)$ 可以避免因舍入导致多算或少算 $1$。

通过双对数变换，我们成功将平方操作转化为加法，从而用简单的贪心解决了问题。