2366. Minimum Replacements to Sort the Array

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long ans = 0;
        int Max = nums.back();
        for(int i = nums.size() - 2; i >= 0; --i) {
            //cout << i << " max = " << Max << " num = " << nums[i] << endl;
            if(nums[i] <= Max) {
                Max = nums[i];
                continue;
            }
            int divisor = nums[i];
            int dividend = Max;
            int mod = divisor % dividend;
            int quotient = divisor / dividend;
            if(mod == 0) {
                ans += quotient - 1;
                continue;
            }
            ans += quotient;
            // binary search to find max Max
            int l = mod, r = Max;
            while(l <= r) {
                int mid = (l + r) >> 1;
                int gap = mid - mod;
                int times = gap / quotient;
                if(gap % quotient != 0) {
                    times++;
                }
                if(mid > dividend - times) r = mid - 1;
                else Max = mid, l = mid + 1;
            }
        }
        return ans;
    }
};


// 11 5
//3 3 5 | 5            11 => 6 5 => 3 3 5
// 16 5                
//4 4 4 4 | 5          16 => 12 4 => 8 4 4 => 4 4 4 4
// 21 5
//4 4 4 4 5 | 5         21 => 16 5 => 12 4 5 => 8 4 4 5 => 4 4 4 4 5
// 26 5																										
//4 4 4 4 5 5 | 5
// ......