Бродячий цирк
Один из шаманов (в те редкие минуты, когда он не строит плотины) работает директором бродячего цирка "Ромашка". Гвоздём программы этого цирка является выступление индийских и африканских слонов на одной сцене.
В цирке есть N слонов, для удобства дрессировки они пронумерованы целыми числами от 1 до N. Цирковой номер со слонами состоит в том, что слоны в каком-то порядке выходят на сцену и развлекают зрительный зал. К примеру, если в цирке было три слона, то выступление может выглядеть как выход слона под номером один, выход слона под номером три, выход слона под номером два.
Для того, чтобы зрители снова и снова возвращались в цирк, директор решил делать каждое представление уникальным. Два представления считаются разными, если слоны в них выступают в разном порядке. Таким образом, каждый новый день слоны выступали в другом порядке, который до этого ни разу не встречался. В случае с тремя слонами они выступали бы в следующем порядке:
Директор каждый день выбирает порядок слонов не слишком оригинально: среди возможных выступлений он выбирает то, в котором слон под номер один выступает раньше всего. Среди таких он выбирает то, в котором слон под номером два выступает раньше всего и т.д.
ЛКШата отправились в цирк на N-ый день. Им очень понравилось представление, и они решили рассказать о нём своим друзьям. К несчастью, они забыли, какой слон выступал первым. Пожалуйста, помогите им! Напишите программу, которая поможет по числу N найти, какой слон выступал первым. Помните, что цирк мог существовать уже довольно долго.
Входные данные
В первой строке входных данных содержится единственное число N (1 ≤ N ≤ 10^5).
Выходные данные
Выведите одно число - искомый номер слона, который выступал первым в N-ый день.