struct Data{
  int index;
  int dis;
  int step;
};


class Solution {
public:
    int jump(vector<int>& arr) {

          int n=arr.size();
          if(n==0){
              return 0;
          }
          int vis[n]={0};
          queue<Data> q;
          Data d;
          d.index=0;
          d.dis=arr[0];
          d.step=0;
          q.push(d);
          vis[0]=1;
          Data f;
          while(!q.empty()){
             f=q.front();
             q.pop();

             if(f.index==n-1){
                  //cout<<f.step<<endl;
                 break;

             }
             int index=f.index+1;
             int dis=f.index+f.dis;
             for(;index<=dis&&index<n;index++){
                 if(vis[index]==0){
                     vis[index]=1;
                     Data newd;
                     newd.dis=arr[index];
                     newd.index=index;
                     newd.step=1+f.step;
                     q.push(newd);
                }
             }

          }
       return f.step;
    }
};