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.

&nbsp;
Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.



Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0. 


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 109


class Solution:
    def minimumReplacement(self, nums) -> int:
        ans = 0
        n = len(nums)
        curr = nums[-1]
        for i in range(n - 2, -1, -1):
            if nums[i] > curr:
                q = nums[i] // curr
                if nums[i] == curr * q:
                    nums[i] = curr
                    ans += q - 1
                else:
                    nums[i] = nums[i] // (q + 1)
                    ans += q
            curr = nums[i]
        return ans
class Solution {
    public long minimumReplacement(int[] nums) {
        long ret = 0L;
        int n = nums.length;
        int last = nums[n - 1];
        for(int i = n - 2;i >= 0; i--){
            if(nums[i] <= last){
                last = nums[i];
                continue;
            }
            if(nums[i] % last == 0){
                // split into nums[i] / last elements, operations cnt = nums[i] / last - 1;
                ret += nums[i] / last - 1;
            }else{
                // split into k elements operations cnt = k - 1;
                int k = nums[i] / last + 1; // ceil
                ret += k - 1;
                last = nums[i] / k; // left most element max is nums[i] / k
            }

        }

        return ret;
    }

}
class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long res=0;
        int n=nums.size();
        int mxm=nums[n-1];
        long long val;
        for(int i=n-2;i>=0;i--)
        {
            // minimum no. of elemetns nums[i] is divided such that every number is less than mxm and minimum is maximized
            val= ceil(nums[i]/(double)mxm); 
            
            // no. of steps is val-1
            res+=(val-1);
            
            // the new maximized minimum value 
            val=nums[i]/val;
            mxm= val;
        }
        return res;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumReplacement = function(nums) {
    const n = nums.length;
    let ans = 0;
    for(let i = n - 2 ; i >= 0 ; i--){
        if(nums[i]>nums[i+1]){
            const temp = Math.ceil(nums[i]/nums[i+1]);
            ans += temp - 1;
            nums[i] = Math.floor(nums[i]/temp);
        }
    }
    return ans;
};
Minimum Replacements to Sort the Array