New Year's Gifts - 2

Santa Claus is arranging candies into packages such that the first package contains 1 candy, the second contains 2 candies, and this pattern continues up to the N-th package, which contains N candies. Snow Maiden wants to make the number of candies in all packages equal by adding one candy to any two different packages each time.

Input

The input consists of a single natural number N (3 ≤ N ≤ 100000000).

Output

Output a single integer representing the minimum number of operations Snow Maiden needs to perform to equalize the number of candies in all packages. If it is not possible to achieve this, output -1.

Examples