You are given a strictly increasing integer array rungs that represents the height of rungs on a ladder. You are currently on the floor at height 0, and you want to reach the last rung.

You are also given an integer dist. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist. You are able to insert rungs at any positive integer height if a rung is not already there.

Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.

&nbsp;
Example 1:

Input: rungs = [1,3,5,10], dist = 2
Output: 2
Explanation:
You currently cannot reach the last rung.
Add rungs at heights 7 and 8 to climb this ladder. 
The ladder will now have rungs at [1,3,5,7,8,10].


Example 2:

Input: rungs = [3,6,8,10], dist = 3
Output: 0
Explanation:
This ladder can be climbed without adding additional rungs.


Example 3:

Input: rungs = [3,4,6,7], dist = 2
Output: 1
Explanation:
You currently cannot reach the first rung from the ground.
Add a rung at height 1 to climb this ladder.
The ladder will now have rungs at [1,3,4,6,7].


&nbsp;
Constraints:


	1 &lt;= rungs.length &lt;= 105
	1 &lt;= rungs[i] &lt;= 109
	1 &lt;= dist &lt;= 109
	rungs is strictly increasing.


class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        rungs=[0]+rungs
        i,ans=1,0
        while i<len(rungs): 
            if rungs[i]-rungs[i-1] > dist:
                ans+=ceil((rungs[i]-rungs[i-1])/dist)-1
            i+=1
        return ans



            
class Solution {
    public int addRungs(int[] rungs, int dist) {
        int ans = 0;
        for (int i=0 ; i<rungs.length ; i++) {
            int d = (i==0) ? rungs[i] : rungs[i] - rungs[i-1];
            if ( d > dist ) {
                ans += d/dist;
                ans += ( d%dist == 0 ) ? -1 : 0;
            }
        }
        return ans;
    }
}
class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) 
    {
         //to keep the track of the number of extra rung to be added
         long long int count = 0;
       
         //our curr pos at the beggining
         long long int currpos = 0;

         //to keep the track of the next pos to be climed
         long long int nextposidx = 0;

         while(true)
         {
             if(currpos == rungs[rungs.size()-1])
             {
                 break;
             }

             if((rungs[nextposidx] - currpos) <= dist)
             {
                 currpos = rungs[nextposidx];
                 nextposidx++;
             }
             else
             {
                 //cout<<"hello"<<endl;
                 long long int temp = (rungs[nextposidx] - currpos);
                 //cout<<"temp = "<<temp<<endl;
                 
                 if((temp%dist) == 0)
                 {
                     long long int val = temp/dist;
                     count = count + (val - 1);
                 }
                 else
                 {
                    long long int val = floor(((temp*1.00)/(dist*1.00)));
                    count = count + (val);
                 }
                 currpos = rungs[nextposidx];
             }
         }
         return count;
    }
};
var addRungs = function(rungs, dist) {
    let res = 0;
    let prev = 0;
    for ( let i = 0; i < rungs.length; i++ ){
        res += Math.floor(( rungs[i] - prev - 1 ) / dist );
        prev = rungs[i];
    }
    return res;
};
Add Minimum Number of Rungs