The sequence of natural numbers from 1 to
`N` must be split into two parts from 1 to
`K` and from
`K+1` to
`N` so that the absolute value of the difference between the sum of the numbers in the first and second part of the sequence is as small as possible. That is, you need to find such a
`K` that the value of the expression
`|\ sum_{i=1}^K\ i\ -\ sum_{ i=K+1}^N\ i\ |` is minimal. For example, for a sequence of numbers from 1 to 4, the split will be minimal for
`K=3` because
`|\ (1+2+3 )-(4)\ |\ =\ 2`, which is less than the difference value for
`K=1` equal to
`| \ (1)-(2+3+4)\ |\ =\ 8` and for
`K=2` equal to
`|\ (1+2)-(3+4)\ |\ =\ 4`.
Write a program that, given `N`, finds the minimum split.
The first line of input contains a single integer `N` (`2\ ≤\ N\ ≤\ 10^9` ).
Output a single integer
`K`. If there are several splitting options, then output the smallest possible
`K`.