Новогодние подарки - 2

Раскладывая конфеты по пакетам, Дед Мороз положил в первый пакет 1 конфетку, во 2-ю – 2, … в N-ю – N. Может ли Снегурочка, докладывая каждый раз в два любых разных пакета по одной конфетке, сделать одинаковым количество конфет во всех подарках?

Технические условия

Входные данные: В единственной строке задано натуральное число N (3 <= N <=100000000).
Выходные данные: Единственное число - наименьшее количество попыток, за которое Снегурочка сможет сравнять содержимое подарков или -1, если сделать это невозможно.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 1
Сложность: 38% 49/79

Пример

Пример входных данных

Пример выходных данных

← Полигон

Список задач