-- yukicoder My Practice
-- author: Leonardone @ NEETSDKASU

import Data.Array
import Data.Bits (popCount)
import qualified Data.Set as Set

main = do
    n <- return . read =<< getLine
    print $ solve [1] [] n 1 Set.empty $ listArray (1, n) [(popCount (x::Int)) | x <- [1..n]]

solve [] [] _ _ _ _ = -1
solve [] nx g c st a = solve nx [] g (c + 1) st a
solve (b:bs) nx g c st a
    | b < 1 || b > g || Set.member b st = solve bs nx g c st a
    | b == g = c
    | otherwise =
        let
            x = a ! b
            st2 = Set.insert b st
        in
            solve bs ((b + x):((b - x):nx)) g c st2 a