+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از بازگشت دامغانیاندی از عملیات موفق خود در قزاقستان، وی متوجه شد ناخواسته ویروس «۱۲۶-نا» (پسر عموی کرونا) را وارد دامغان کرده است. دامغان، شهری به شکل دایره‌است که $n$ خانه دور آن قرار دارند. او متوجه شد که افراد دقیقا یکی از خانه‌های دامغان به این ویروس مبتلا شده‌اند. وی برای نجات شهر خود، دست به دامن شاختک شد. شاختک به دامغانیاندی قول تعدادی بمب ضد ویروس را داد. دامغانیاندی در هر مرحله‌ی پاکسازی، یک خانه را انتخاب کرده و یکی از بمب‌های ضد ویروس را داخل آن خانه می‌اندازد. با این کار، خانه‌ی مورد نظر و دو خانه‌ی مجاور آن دور دایره، پاکسازی می‌شوند. (به بیانی دیگر، اگر ویروس در آن خانه‌ها باشد می‌میرد.) ویروس ۱۲۶-نا بسیار هوشمند بوده و پس از مطلع شدن از انفجار یک بمب، در هر مرحله یا در خانه‌ی فعلی می‌ماند و یا به یکی از دو خانه‌ی مجاور می‌جهد. توجه کنید زمانی که ویروس از خانه‌ی $i$ به خانه‌ی $j$ بجهد، اهالی خانه‌ی $i$ دیگر به ویروس مبتلا نخواهند بود و تنها اهالی خانه‌ی $j$ مبتلا هستند. از آنجایی که بمب‌های ضد ویروس بسیار پر هزینه هستند، دامغانیاندی قصد دارد کمینه‌ی تعداد بمب‌های لازم برای پاک‌سازی قطعی دامغان را برای خرید محاسبه کند. این مقدار را برای او به دست آورید. # ورودی در تنها سطر ورودی عدد $n$ داده می‌شود که تعداد خانه‌های دامغان می‌باشد. $$1 \le n \le 100$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که کمینه‌ی تعداد بمب‌های ضد ویروس برای پاک‌سازی قطعی دامغان است. ## ورودی نمونه ۱ ``` 4 ``` ## خروجی نمونه ۱ ``` 2 ``` توضیح:  ابتدا دامغانیاندی بر خانه‌ی قرمز در شکل «۱» بمب می‌اندازد. حال اگر ویروس در سه خانه‌ی سبز شکل «۲» باشد، می‌میرد. پس در نظر بگیرید در خانه‌ی غیر سبز باشد. پس از حرکت ویروس، می‌دانیم آن در خانه‌ی سیاه شکل «۳» نمی‌تواند حضور داشته باشد. پس دامغانیاندی بر خانه‌ی قرمز شده شکل «۳» بمب می‌اندازد تا مطمئن باشد ویروس می‌میرد. ## ورودی نمونه ۲ ``` 7 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 2 ``` ## خروجی نمونه ۳ ``` 1 ```

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