Escape the Spiral Maze

You find yourself trapped in an infinite maze where the cells are numbered in a spiral pattern as shown in the figure below.

In the maze, each cell contains a unique positive integer. A black line between any two cells indicates that there is a wall between them; if there is no black line, you can move freely between the two cells.

You start at the cell labeled \(1\) and your exit is located at the cell labeled \(n\). Due to an earthquake, some of the walls have fallen, opening new paths and allowing you to move between cells that were previously separated. Taking advantage of the chaos, you want to escape using as few cells as possible.

Your task is to determine the minimum number of moves required to reach cell \(n\) from cell \(1\) under these conditions.

Spiral Coordinate Interpretation

The numbering of the maze follows a spiral pattern with cell \(1\) at the center at coordinate \((0,0)\). For \(n > 1\), the cell \(n\) lies on a ring with radius \(r\) (where \(r\) is the smallest integer such that \(n \le (2r+1)^2\)). It can be shown that the minimum number of moves is given by the formula:

[ \text{moves} = r + \min_{0 \leq k \leq 3} \left| n - \left((2r+1)^2 - r - k \cdot (2r) \right)\right| ]

If \(n=1\), you are already at the exit and no moves are needed.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 10^{12}\)), representing the label of the exit cell.

outputFormat

Output a single integer, the minimum number of moves required to go from cell \(1\) to cell \(n\) in the maze.

sample

1

0