• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۵۰ مگابایت

در کشوری رییس جمهور به این نحو انتخاب می‌شود:

اگر n نفر کاندید شده باشند ، ابتدا طی مراسمی با قرعه کشی به هر کاندیدی یک عدد از ۱ تا n تعلق می‌گیرد. کاندیدها به ترتیب شماره‌هایشان، دور میزی می‌نشینند و یکی در میان با شروع از شماره‌ی ۲ حذف می‌شوند.

حالا شما با استفاده از تابع بازگشتی برنامه‌ای بنویسید که شماره‌ی کاندید پیروز را با گرفتن تعداد کاندیدها از ورودی چاپ کند.

ورودی

در تنها خط ورودی عدد $n$ آمده است.

خروجی

در تنها خط خروجی شماره‌ی کاندیدا‌ پیروز را چاپ کنید.

مثال

ورودی نمونه ۱

12

خروجی نمونه ۱

9

ورودی نمونه ۲

16

خروجی نمونه ۲

1