Rączy jelonek

Limit pamięci: 64 MB

Rączy jelonek zmierza długimi susami na polanę. Rozpiera go energia, więc każdy jego skok może być nawet dwa razy dłuższy od poprzedniego.

Formalnie rzecz ujmując, w każdym momencie energia jelonka jest na określonym poziomie . Jelonek ma dwie możliwości ruchu:

• skok o metrów w przód lub w tył, powodujący automatyczne przełączenie na poziom energii ,
• skok wzwyż, który nie powoduje przemieszczenia na drodze do polany oraz skutkuje przełączeniem na poziom .

Początkowo, jelonek ma energię równą . W momencie, gdy jego energia jest równa i jelonek skoczy wzwyż, zatrzymuje się.

Poniżej przedstawiono przykładową podróż rączego jelonka, która rozpoczęła się w punkcie po lewej stronie drogi. Numery nad strzałkami oznaczają poziom energii jelonka po danym skoku. Wartość oznacza, że jelonek się zatrzymał.

Droga prowadząca do polany jest nieskończona w obydwóch kierunkach. Oznacza to, że jelonek w trakcie podróży może znaleźć się za polaną lub przed punktem, z którego wyrusza. Jelonka od celu dzieli początkowo metrów. Oblicz, jaka jest najmniejsza liczba skoków, która pozwoli mu dotrzeć do polany i zatrzymać się tam.

Wejście

Pierwsza linia wejścia, zawiera jedną liczbę całkowitą () oznaczająca odległość pomiędzy jelonkiem a polaną. Dodatkowo, w testach wartych sumarycznie punktów, .

Wyjście

Wypisz jedną liczbę całkowitą równą minimalnej liczbie skoków, które musi wykonać jelonek, aby dotrzeć do polany i zatrzymać się.

Przykład

Dla danych wejściowych:

6

poprawną odpowiedzią jest:

9