Nested Squares Movement Minimization

We are given n nested squares on the plane. The i-th square has side length i for i = 1,2,...,n and is uniquely determined by the coordinates of its top‐left corner \( (x_i,y_i) \). Initially, the squares are arranged so that any square with a smaller index is completely contained in any square with a larger index. In other words, for every \( 1 \le i < j \le n \) the square \( i \) is contained in square \( j \) (the containment includes the boundary).

You are allowed to move at most one square in each step. A move consists of shifting a square one unit in one of the four cardinal directions (up, down, left or right). During the process, the following invariant must be maintained: if square \( i \) and square \( j \) with \( i<j \) are at positions \( (x_i,y_i) \) and \( (x_j,y_j) \) respectively, then square \( i \) must be contained in square \( j \). In terms of the coordinates and side lengths, since square \( i \) has side length \( i \) and square \( j \) has side length \( j \), the containment condition is

[ x_j \le x_i \quad\text{and}\quad y_j \le y_i \quad\text{and}\quad x_i+i \le x_j+j \quad\text{and}\quad y_i+i \le y_j+j. ]

The goal is to move only the smallest square (the one with side length 1) from its initial position \( (0,0) \) to a given target coordinate \( (x_{\rm end},y_{\rm end}) \) while ensuring that the invariant is maintained at every step. It turns out that if no other square is moved, then the allowed positions for square 1 are very limited. In fact, if square 2 is at \( (0,0) \) then square 1 must lie in the region

[ { (x,y):; 0\le x\le 1,; 0\le y\le 1 }. ]

In order to allow square 1 to reach \( (x_{\rm end},y_{\rm end}) \) (which may lie outside such a small region), some of the larger squares must be moved as well. However, you are free to choose which squares to move (one at a time) and in which order, as long as the containment invariant (that every smaller square is contained in every larger square) remains valid after every single move.

Your task is to compute the minimum number of moves required so that, after some sequence of moves, the smallest square is located at \( (x_{\rm end},y_{\rm end}) \). The moves are measured in unit steps.

---

An Equivalent Reformulation

You may think of the final configuration in a nice synchronized form where all squares have the same top‐left coordinate. In fact, one optimal strategy is to have the final positions of the squares satisfy

[ s_1 = s_2 = \cdots = s_n = (x_{\rm end}, y_{\rm end}). ]

This is allowed because if all squares share the same top‐left coordinate then for any \( i<j \) we have

[ x_j = x_{\rm end} \le x_{\rm end} = x_i \quad\text{and}\quad x_i+ i \le x_{\rm end}+j, \quad\text{since}\quad i\le j, ]

and similarly for the \( y \) coordinates.

A careful analysis shows that the minimum number of moves required is given by processing the horizontal and vertical moves separately. Without loss of generality, assume that \( x_{\rm end} \ge 0 \) (the case when \( x_{\rm end} < 0 \) is analogous by symmetry). To finally have the smallest square at \( x_{\rm end} \), one may choose the final positions of the squares so that

[ s_n = x_{\rm end} - D, \quad s_{n-1} = x_{\rm end} - D + \delta_{n-1}, \quad s_{n-2} = x_{\rm end} - D + \delta_{n-1}+\delta_{n-2}, \quad \ldots, \quad s_1 = x_{\rm end}, ]

where each \( \delta_i \) is either 0 or 1 and \( D = \min(x_{\rm end},n-1) \). The cost (i.e. number of moves) in the horizontal direction is then the sum of the distances each square is moved. Since all squares start at 0, the minimal horizontal cost is

[ \text{Cost}x = n\cdot (x{\rm end} - D) + \frac{D(D+1)}{2}. ]

A similar formula holds for the vertical direction. Therefore, if we let

[ D = \min(|x_{\rm end}|, n-1) \quad\text{and}\quad E = \min(|y_{\rm end}|, n-1), ]

then the minimum number of moves required is

[ \text{Answer} = n\Bigl((|x_{\rm end}| - D) + (|y_{\rm end}| - E)\Bigr) + \frac{D(D+1)+E(E+1)}{2}. ]

</p>

You are given the integer \( n \) and the target coordinates \( x_{\rm end} \) and \( y_{\rm end} \) (they may be negative). Compute the minimum number of moves required.

inputFormat

The input consists of a single line containing three integers: n, x_end and y_end, where n (1 ≤ n ≤ 10⁵) is the number of squares and x_end and y_end (|x_end|, |y_end| ≤ 10⁹) specify the target coordinates \( (x_{\rm end}, y_{\rm end}) \) for the smallest square.

outputFormat

Output a single integer, the minimum number of moves required to move the smallest square to \( (x_{\rm end}, y_{\rm end}) \) while keeping the invariant that every smaller square is contained in every larger square.

sample

2 1 1

2