В крайних клетках полоски шириной в одну клетку и длиной в $$$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.