use std::io::Read; fn main() { let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let n: usize = buf.trim().parse().unwrap(); if n == 1 { println!("1"); return } let mut positions: Vec = vec![1]; let mut is_checked: Vec = vec![false; n+1]; let mut layer: usize = 1; 'outer: loop { layer += 1; let mut new_positions: Vec = vec![]; for p in positions.iter() { let ones: usize = p.count_ones() as usize; let forward: usize = p + ones; let backward: usize = p.saturating_sub(ones); if forward == n || backward == n { println!("{}", layer); break 'outer; } if forward > 1 && forward < n && !is_checked[forward] { new_positions.push(forward); is_checked[forward] = true; } if backward > 1 && backward < n && !is_checked[backward] { new_positions.push(backward); is_checked[backward] = true; } } if new_positions.is_empty() { println!("-1"); break 'outer; } positions = new_positions; } }