#include <iostream> #include <algorithm> #include <functional> #include <string> using namespace std; void calc(int step, int go[], int min[], int from, int to){ if(step < min[from]){ min[from] = step; //前に進む if(from + go[from] <= to){ calc(step + 1, go, min, from + go[from], to); } //後ろに進む if(from - go[from] >= 0){ calc(step + 1, go, min, from - go[from], to); } } } int main(){ //始まりの数値は1 const int Max = 10000; int go[Max] = {0}; int min[Max]; int n; int least; cin >> n; //移動可能数算出 for(int i=0; i<n; i++){ least = i + 1; while(least > 0){ if(least % 2 == 1){ go[i] ++; } least /= 2; } } //min表初期化 for(int i=0; i<n; i++){ min[i] = 99999; } //移動最低数算出(再帰) calc(1, go, min, 0, n-1); //結果出力 if(min[n-1] == 99999){ cout << -1 << endl; }else{ cout << min[n-1] << endl; } //全て出力 /* cout << endl; for(int i=0; i<n; i++){ cout << min[i] << endl; } */ return 0; }