+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  امتحانات میان‌ترم نزدیک است و وضعیت هندسه‌ی کاراکترهای کمکی خراب! این موضوع به شدت روی اعتماد به نفس کاراکتر‌های کمکی اثر گذاشته و کاراکتر اصلی ۱ را به فکر انداخته تا برای آن‌ها کلاس تقویتی تشکیل دهد. از بین کاراکترهای کمکی $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 ```

حل سؤال در بانک سؤالات