#include #include #include #include #include #include #include #define rep(i, n) for(int (i)=0; (i)<(n); ++(i)) #define INF 1000000 using namespace std; int count_1(int n) { int x = 0; while(n > 0) { x += n % 2; n >>= 1; } return x; } typedef map > G; typedef map Visited; G create_matrix(int n) { G g; for(int i=1; i<=n; ++i) { int count = count_1(i); int a = i - count < 1 ? -1 : i - count; int b = i + count > n ? -1 : i + count; g[i] = pair(a, b); } return g; } int walk(Visited& v, G g, int n, int x, int s) { if(x == n) { return s; } v[x] = true; int l = INF, r = INF; if(g[x].first != -1 && !v[g[x].first]) { l = walk(v, g, n, g[x].first, s+1); } if(g[x].second != -1 && !v[g[x].second]) { r = walk(v, g, n, g[x].second, s+1); } v[x] = false; return min(l, r); } Visited get_visited(int n) { Visited v; rep(i, n) { v[i+1] = false; } return v; } int main() { int n; cin >> n; Visited v = get_visited(n); G g = create_matrix(n); int r = walk(v, g, n, 1, 1); cout << (r == INF ? -1 : r) << endl; return 0; }