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

امتحانات میان‌ترم نزدیک است و وضعیت هندسه‌ی کاراکترهای کمکی خراب! این موضوع به شدت روی اعتماد به نفس کاراکتر‌های کمکی اثر گذاشته و کاراکتر اصلی ۱ را به فکر انداخته تا برای آن‌ها کلاس تقویتی تشکیل دهد.

از بین کاراکترهای کمکی $n$ نفر در این کلاس تقویتی ثبت‌نام کرده‌اند. کلاس تقویتی در کلاسی که $n$ نیمکت آن پشت سر هم و در یک ردیف چیده شده‌اند، برگزار می‌شود. نیمکت‌ها از جلوی کلاس تا انتها با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند.

کاراکتر اصلی ۱ در اولین روز تدریسش برای کاراکترهای کمکی متوجه الگوی عجیبی در نشستن کاراکترهای کمکی روی نیمکت‌ها شد. کاراکتر کمکی ۱ که می‌آید روی نیمکت شماره‌ی ۱ می‌نشیند و از کاراکتر کمکی ۲ تا کاراکتر کمکی $n$ نیمکت استرس‌زدا را شناسایی می‌کنند و روی آن می‌نشینند.

نیمکتی را استرس‌زدا می‌نامیم که:

• خالی باشد.
• بیشینه فاصله را تا نزدیک‌ترین نیمکت پر داشته باشد. (واحد فاصله در اینجا تعداد نیمکت‌های بین است)
• اگر چند نیمکت با بیشینه فاصله موجود بود، نیمکتی که شماره‌ی آن از بقیه‌ کم‌تر باشد.

از آنجایی که کاراکتر اصلی ۱ حوصله ندارد تا نشستن کاراکتر کمکی $n$ صبر کند، پس برنامه‌ای بنویسید که شماره‌ی نیمکتی که کاراکتر کمکی $n$ طبق الگو در آن می‌نشیند را چاپ کند.

ورودی

در تنها خط ورودی عدد طبیعی $n$ داده می‌شود.

$$1 \leq n \leq 10^{100 \ 000}$$

خروجی

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

مثال

ورودی نمونه

10

خروجی نمونه

9

توضیح

در مثال داده شده، کاراکتر کمکی ۱ طبق صورت سوال در نیمکت ۱ می‌نشیند.

#  # # # # # # # # 1
10 9 8 7 6 5 4 3 2 1

نیمکت استرس‌زدا برای کاراکتر کمکی ۲ نیمکت ۱۰ است، چون با تنها نیمکت پر یعنی نیمکت ۱ بیشترین فاصله را دارد.

2  # # # # # # # # 1
10 9 8 7 6 5 4 3 2 1

برای کاراکتر کمکی ۳، نیمکت‌های ۵ و ۶ هر دو فاصله‌شان تا نزدیک‌ترین نیمکت پر ۳ است و نیمکتی با فاصله‌ی کمتر تا نزدیک‌ترین نیمکت پُرَش وجود ندارد. از بین این دو نیمکت ۵ استرس‌زداست چون شماره‌اش نسبت‌ به نیمکت ۶ کوچکتر است.

2  # # # # 3 # # # 1
10 9 8 7 6 5 4 3 2 1

برای کاراکتر کمکی ۴، ۳ نیمکت وجود دارد که فاصله‌شان تا نزدیک‌ترین نیمکت پر ۱ باشد و بقیه‌ی نیمکت‌های خالی با نزدیک‌ترین نیمکت پر همسایه هستند (فاصله‌شان ۰ است). پس از بین آن ۳ نیمکت که شماره‌هایشان ۳، ۷ و ۸ است، نیمکت ۳ استرس‌زداست.

2  # # # # 3 # 4 # 1
10 9 8 7 6 5 4 3 2 1