Let \(M = \log_2 \max A\ (= 60)\).

First, consider the following problem, obtained by converting numbers in binary to 01 strings.

You are given a sequence \(S = (S_1, S_2, \ldots, S_N)\) of 01 strings of length \(N\).

Consider performing the following series of operations on \(S\):

• Choose a pair of integers \((l, r)\) satisfying all of the following conditions:
  • \(1 \le l \le r \le N\)
  • The last characters of \(S_l, S_{l+1}, \ldots, S_r\) are all the same.
• For each \(k = l, l+1, \ldots, r\), delete the last character of \(S_k\).

Find the minimum number of operations needed to make all elements of \(S\) the empty string.

The answer to this problem is \(\displaystyle \sum_{i=1}^N |S_i| - \sum_{i=1}^{N-1} \text{LCS}(S_i, S_{i+1})\), which can be seen by considering deleting adjacent strings simultaneously as much as possible.

We use this to solve the original problem.

---

Considering that operations are possible even when \(A_i = 0\), the problem reduces to:

Let \(S_i\) be the binary string representation of \(A_i\), and let \(S_i^k\) be the string obtained by prepending \(k\) copies of 0 to \(S_i\). Find the minimum value of \(\displaystyle \sum_{i=1}^N \left(|S_i| + c_i\right) - \sum_{i=1}^{N-1} \text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\) over all sequences of non-negative integers \(c = (c_1, c_2, \ldots, c_N)\).

Thus, it suffices to be able to compute the following two things:

1. Compute \(\text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\) efficiently.
2. Using 1, compute the minimum value of \(\displaystyle \sum_{i=1}^N \left(|S_i| + c_i\right) - \sum_{i=1}^{N-1} \text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\) via DP.

Note that the maximum value of \(c_i\) in the optimal solution is not necessarily at most \(60\).

---

1. Computing \(\text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\)

Letting \(m = \min(c_i, c_{i+1})\), we have \(\text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}}) = \text{LCS}(S_i^{c_i - m}, S_{i+1}^{c_{i+1} - m}) + m\). Since at least one of \(c_i - m\) and \(c_{i+1} - m\) is \(0\), it suffices to compute \(\text{LCS}(S_i^k, S_{i+1})\) and \(\text{LCS}(S_i, S_{i+1}^k)\) for each \(k\). Noting that for \(k \ge 60\) each of these values is always the same, each can be computed in \(O(M^2)\) using the standard LCS DP approach.

2. Computing the minimum value of \(\displaystyle \sum_{i=1}^N \left(|S_i| + c_i\right) - \sum_{i=1}^{N-1} \text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\)

Define \(d[k][v]\) as “the minimum value of \(\displaystyle \sum_{i=1}^k (|S_i| + c_i) - \sum_{i=1}^{k-1} \text{LCS}(S_i^{c_i}, S_{i+1}^{c_{i+1}})\) when \(c_1\) through \(c_k\) are determined and \(c_k = v\).” Note that we need to compute this for the range \(1 \le k \le N\), \(0 \le v \le \color{red}(N-1)M\color{black}\). This DP can be computed in \(O(N^3 M^2)\) time.

---

By implementing the above appropriately, you can solve this problem. The time complexity is \(O(N^3 M^2)\).

By speeding up the DP, it is also possible to solve this in \(O(N^2 M^2)\) time.

Implementation example (Python3)

import sys

input = sys.stdin.readline
M = 60
INF = 10**9


def f(s: str, t: str):
    s += "0" * M
    n, m = len(s), len(t)
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                d[i + 1][j + 1] = d[i][j] + 1
            else:
                d[i + 1][j + 1] = max(d[i][j + 1], d[i + 1][j])
    ans = []
    for i in range(n - M, n + 1):
        ans.append(d[i][m])
    return ans


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = ["" if x == 0 else bin(x)[2:][::-1] for x in a]
    L = M * (n + 1) + 1
    d = [j for j in range(L)]
    for i in range(n - 1):
        dd = [INF] * L
        r1 = f(s[i], s[i + 1])
        r2 = f(s[i + 1], s[i])
        for j1 in range(L):
            for j2 in range(L):
                if j1 < j2:
                    dd[j2] = min(dd[j2], d[j1] + j2 - j1 - r2[min(M, j2 - j1)])
                else:
                    dd[j2] = min(dd[j2], d[j1] + j2 - j2 - r1[min(M, j1 - j2)])
        d = dd
    print(sum(len(x) for x in s) + min(d))

---

Proposed by: sounansya