eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Бродячий цирк

Бродячий цирк

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Один з шаманів (у ті рідкі хвилини, коли він не будує греблі) працює директором бродячого цирка "Ромашка". Стержнем програми цього цирку є виступ індійських та африканських слонів на одній сцені.

У цирку є N слонів, для зручності дресирування вони пронумеровані цілими числами від 1 до N. Цирковий номер зі слонами полягає у тому, що слони у якомусь порядку виходять на сцену і веселять зал з глядачами. Наприклад, якщо у цирку було три слони, то виступ може виглядати як вихід слона під номером один, вихід слона під номером три, вихід слона під номером два.

Для того, щоб глядачі знову і знову повертались у цирк, директор вирішив робити кожну виставу унікальною. Дві вистви вважаються різними, якщо слони в них виступають у різному порядку. Таким чином, кожного нового дня слони виступали у іншому порядку, який до цього жодного разу не зустрічався. У випадку з трьома слонами вони виступали б у наступному порядку:

Директор кожного дня обирає порядок слонів не дуже оригінально: серед можливих виступів він обирає той, у якому слон під номер один виступає раніше усіх. Серед таких він обирає той, у якому слон під номером два виступає раніше усіх і т.д.

ЛКШенята відправились до цирку на N-ий день. Їм дуже сподобалась вистава, і вони вирішили розповісти про неї своїм друзям. На жаль, вони забули, який слон виступав першим. Будь-ласка, допоможіть їм! Напишіть програму, яка допоможе за числом N знайти, який слон виступав першим. Пам'ятайте, що цирк міг існувати вже досить давно.

Вхідні дані

У першому рядку вхідних даних міститься єдине число N (1N10^5).

Вихідні дані

Виведіть одне число - шуканий номер слона, який виступав першим у N-ий день.

Приклад

Вхідні дані #1
3
Вихідні дані #1
2