ドミノを左から順に置いていくことを考えましょう。
末尾にドミノ \(i\) が置かれている時、次に置けるドミノ \(j\) は \(S_j \leq 2 S_i\) を満たすドミノです。この条件は \(S_i\) が大きければ大きいほど緩和されます。よって、毎回できるだけ大きいドミノを置いていく方がよいことがわかります。
ここから、以下の貪欲法が動作します。

• はじめにドミノ \(1\) を左端に置く。
• 以下の操作を繰り返す。
  • 現在一番右に置かれているドミノをドミノ \(i\) とする。
  • \(2 S_i \geq S_N\) が成り立つ場合、ドミノ \(N\) を右端に置いて操作を終了して、現在置いたドミノの個数を出力する。
  • そうでない、すなわち \(2S_i \lt S_N\) の場合を考える。\(2S_i \geq S_j\) を満たすドミノ \(j\) のうち最大のものを選ぶ。
    • 条件を満たす \(j\) が存在しないか \(S_i \geq S_j\) である場合、これ以降も \(S_i\) より大きいドミノが置けることはないので、ドミノ \(N\) も置けない。よって \(-1\) を出力してアルゴリズムを終了する。
    • そうでない場合、ドミノ \(i\) の右にドミノ \(j\) を置く。
• 操作を終了した時点で置いたドミノの個数を出力して、アルゴリズムを終了する。

この貪欲はドミノを置いた個数を \(K\) として \(\mathrm{O}(K N)\) 回で終了します。そして、これは少し難しいのですが \(K\) は高々 \(60\) 回 (\( = 2 \lceil \log_2 \max(A) \rceil\) 回) であることが証明できます。

(証明) 最終的においたドミノの大きさの列を \(s_1, s_2, \dots, s_K\) とする。ここで \(s_1, s_2, s_3\) に注目する。もし \(s_1 \times 2 \geq s_3\) の場合、\(s_2\) を飛ばして \(s_3\) が置けることになりアルゴリズムに矛盾する。よって \(s_1 \times 2 \lt s_3\) 、すなわち \(s_3\) は \(s_1\) の \(2\) 倍より大きい。
同様にして \(s_{i+2}\) は \(s_i\) の \(2\) 倍大きいことが証明できるため、仮に \(K \geq 61\) とすると \(s_{61}\) は \(s_1\) の \(2^{30}=1073741824\) 倍より大きいことになるが、これは入力の制約 \(A_i \leq 10^9\) に反する。よって \(K \leq 60\) であることが示された。

よってこの問題を \(\mathrm{O}(N \log \max(A))\) 回で解くことができて、これは十分高速です。

• 実装例 (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();
}