When making \(K\) pairs of kagamimochi \((0\leq K\leq\dfrac N2)\), we may assume that we use the first \(K\) mochi’s and the last \(K\) mochi’s. (If a mochi on the top of a kagamimochi is not in the first \(K\) mochi’s, we can substitute it with one of them. The same applies to the last \(K\) mochi’s too.)
Also, when \(K\) mochi’s for the top and \(K\) mochi’s for the bottom are fixed, one can make \(K\) pairs of kagamimochi’s if and only if one can pair them by taking the smallest one from each group. (\(\Leftarrow\) is obvious; \(\Rightarrow\) is prove as follows: consider sorting the kagamimochi’s in ascending order of the sizes of the top one. If the bottom one is not sorted, then swapping the unordered pair still form \(K\) valid kagamimochi’s.)

Thus, for a fixed \(K\), one can determine if \(K\) pairs of kagamimochi can be made in \(O(K)\) time.

If one can make \(k\) pairs for some \(k\), then one can make \(l\) pairs for all \(l\ (l\leq k)\), so the problem can be solved with binary searching.

The time complexity is \(O(N\log N)\).

#include <algorithm>
#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;

    vector<unsigned> A(N);
    for (auto&& a : A)
        cin >> a;

    // Decision function
    // Can we make K pairs?
    const auto check{
        [N, &A](unsigned K) {
            for (unsigned i = 0; i < K; ++i)
                // Take the first K and the last K
                if (A[i] * 2 > A[N - K + i])
                    // If any pair is invalid, return false
                    return false;
            // Otherwise, return true
            return true;
        }
    };

    // Use binary search to find the maximum value between 0 and N/2 for which the decision function is true (in other words, minimum value with false minus one)
    cout << *ranges::partition_point(views::iota(0U, N / 2 + 1), check) - 1 << endl;

    return 0;
}