Consider placing dominoes from the left.
If domino \(i\) is placed at the end, the next domino that we can place is the one that satisfies \(S_j \leq 2 S_i\). The larger \(S_i\) is, the more this condition is relaxed. Thus, it is better to place as large a domino as possible.
Therefore, the following greedy algorithm is valid.

• Place domino \(1\) at the left end.
• Repeat the following operation.
  • Let domino \(i\) be the rightmost domino placed.
  • If \(2 S_i \geq S_N\), place domino \(N\) at the end, terminate the procedure, and report the number of dominoes placed so far.
  • Otherwise (i.e. if \(2S_i \lt S_N\)), find the maximum \(j\) such that \(2S_i \geq S_j\).
    • If no \(j\) satisfies the condition, or \(S_i \geq S_j\), then we can never place a domino larger than \(S_i\), so we cannot place domino \(N\). Print \(-1\) and terminate the algorithm.
    • Otherwise, place domino \(j\) to the right of domino \(i\).
• Print the number of dominoes placed so far when the procedure ends, and terminate the algorithm.

This greedy algorithm finishes after \(\mathrm{O}(K N)\) times, where \(K\) is the number of times the domino was placed. Also, one can prove that \(K\) is at most \(60\) (\( = 2 \lceil \log_2 \max(A) \rceil\)), although the proof is not very easy.

(Proof) Let \(s_1, s_2, \dots, s_K\) be the sequence of the sizes of dominoes placed. If \(s_1 \times 2 \geq s_3\), it means \(s_3\) can be placed without placing \(s_2\), violating the algorithm. Therefore, \(s_1 \times 2 \lt s_3\), so \(s_3\) is greater than two times \(s_1\).
Similarly, one can prove that \(s_{i+2}\) is at least twice as large as \(s_i\). If you assume \(K \geq 61\), then \(s_{61}\) turns out to be \(2^{30}=1073741824\) times as large as \(s_1\), but it violates the input constraints \(A_i \leq 10^9\). Hence, it has been prove that \(K \leq 60\).

Therefore, the problem has been solved in \(\mathrm{O}(N \log \max(A))\) steps, which is fast enough.

• Sample code (C++)

#include <iostream>
#include <vector>
using namespace std;

void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (auto& a : A) cin >> a;

  vector<int> used(N);
  int ans = 1, last = 0;
  while (true) {
    if (A[last] * 2 >= A[N - 1]) {
      ans += 1;
      break;
    }
    int nxt = -1;
    for (int i = 1; i <= N - 1; i++) {
      if (used[i]) continue;
      if (A[last] * 2 >= A[i]) {
        if (nxt != -1 && A[nxt] >= A[i]) continue;
        nxt = i;
      }
    }
    if (nxt == -1 || A[nxt] <= A[last]) {
      cout << -1 << endl;
      return;
    }
    ans++, last = nxt, used[nxt] = 1;
  }
  cout << ans << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) solve();
}