2366. Minimum Replacements to Sort the Array

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

• For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return the minimum number of operations to make an array that is sorted in non-decreasing order.

class Solution {
public:
    long long minimumReplacement(vector<int>& A) {
        long long res = 0, mi = 1e9, n = A.size();
        for(int i = n - 1; i >= 0; i--) {
            long long now = (A[i] + mi - 1) / mi;
            mi = A[i] / now;
            res += now - 1;
        }
        return res;
    }
};