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(); }