Ciąg

Limit pamięci: 32 MB

Jaś niedawno usłyszał w szkole o ciągach liczbowych. Bardzo mu się one spodobały i szybko zaczął tworzyć swoje własne, długie sekwencje liczb. Jego najnowszym wymysłem jest ciąg - niemalejąca sekwencja liczb naturalnych o następującej własności: dla każdej liczby naturalnej zawiera ona dokładnie wystąpień liczby . (Zakładamy przy tym, że nie jest liczbą naturalną). Innymi słowy, dla każdego dokładnie spośród liczb jest równe .

Pierwszych kilka wyrazów ciągu udało się Jasiowi wypisać, ale kartka i długopis okazały się niewystarczające, aby wygenerować jakiś dłuższy początkowy fragment ciągu. Pomóż Jasiowi uporać się z tym problemem.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę naturalną ,
• wyznaczy -ty wyraz ciągu ,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę naturalną () - numer szukanego wyrazu ciągu.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę naturalną .

Przykład

Dla danych wejściowych:

5

poprawną odpowiedzią jest:

3

Wyjaśnienie do przykładu: oznacza, że w ciągu liczba występuje dokładnie razy; dokładniej, .

Uwaga: Możesz założyć, że w co najmniej 40% testów jest spełniony warunek , a w co najmniej 70% testów - warunek .

Autor zadania: Wojciech Tyczyński.