Arithmetic Exercise

At the end of the lesson, the arithmetic teacher assigned homework, but Vova was eager to get to recess and forgot to write it down. Now at home, he's trying to recall the assignment. He remembers it involved several of the first natural numbers, each preceded by either a plus or minus sign, and there were no parentheses:

[ ? 1 ? 2 ? 3 ? ...? N = ]

He also managed to glance at the teacher's book and knows that the result is an integer (k). Vova now wants to reconstruct the example from the assignment.

Input

The input consists of a single integer (k) (|k| ≤ 10^100000).

Output

Output the smallest natural number (N) ((N ≥ 1)) for which there exists at least one combination of signs in the example that results in the integer (k).

Examples