class Solution {

 public:

     int dp[];

     struct Node{

         int pos;

         int speed;

         int step;

         Node(int p,int s,int ss){

             pos=p;

             speed=s;

             step=ss;

         }

     };

     int racecar(int target) {

         queue<Node> Q;

         set<pair<int,int> > vis;

         Q.push(Node(,,));

         vis.insert({,});

         while(!Q.empty()){

             Node q=Q.front();

             Q.pop();

             if(q.pos==target) return q.step;

             if(vis.find({q.pos+q.speed,q.speed*})==vis.end()&&q.pos+q.speed>=&&q.pos+q.speed<=*target){

                 vis.insert({q.pos+q.speed,q.speed*});

                 Q.push(Node(q.pos+q.speed,q.speed*,q.step+));

             }

             if(vis.find({q.pos,q.speed>?-:})==vis.end()){

                 vis.insert({q.pos,q.speed>?-:});

                 Q.push(Node(q.pos,q.speed>?-:,q.step+));

             }

         }

         return -;

     }

 };

 class Solution {

 public:

     int dp[];

     int racecar(int target) {

         if(dp[target]!=) return dp[target];

         int bound;

         for(int i=;i<;i++){

             if((<<i)-==target) return dp[target]=i;

             if((<<i)->target){

                 bound=i;

                 break;

             }

         }

         dp[target]=bound++racecar((<<bound)--target);

         for(int i=;i<bound-;i++){

             dp[target]=min(dp[target],bound-++i++racecar(target-(((<<(bound-))-)-((<<i)-))));

         }

         return dp[target];

     }

 };