410516: GYM104033 1 Лягушка и кузнечик

1. Лягушка и кузнечикограничение по времени на тест0.5 секундограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В крайних клетках полоски шириной в одну клетку и длиной в $$$N$$$ клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № $$$N$$$. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?

Входные данные

Единственная строка входных данных содержит целое число $$$N$$$ — длину клетчатой полосы ($$$2 \leq N \leq 2\cdot 10^9$$$).

Выходные данные

Если лягушка и кузнечик могут оказаться в одной клетке, требуется вывести одно целое число — минимальное количество секунд, через которое они встретятся. Если они не смогут оказаться в одной клетке, требуется вывести число «-1» (без кавычек).

Система оценки

Решения, правильно работающие при $$$N \leq 30$$$, будут оцениваться в 30 баллов.

Решения, правильно работающие при $$$N \leq 10^5$$$, будут оцениваться в 50 баллов.

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

5

Выходные данные

1

Входные данные

9

Выходные данные

2

Примечание

В первом примере лягушка может прыгнуть из клетки 1 в клетки 3 и 4, а кузнечик может прыгнуть из клетки 5 в клетки 3 и 4. Поэтому через 1 секунду они могут оказаться в одной клетке.

Во втором примере лягушка и кузнечик могут встретиться через 2 секунды. Например, лягушка прыгает в клетку 3, затем в клетку 6, а кузнечик прыгает в клетку 8, затем в клетку 6.