- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
چرزه و پشمک اخیرا کولههای خود را بستهاند و تصمیم گرفتهاند که دنیا را در ۷۹ روز طی کنند. اما آنها در طی جهانگردیشان با مسائلی روبهرو میشوند و از شما میخواهند که آنها را برایشان حل کنید.
اکنون آنها به دلیلی (!) وارد کازان روسیه شدهاند و میخواهند برای مدتی در آن جا اتراق کنند.
آنها هنگام ورود به کازان، از آن جایی که سه مشکل مرگبار را گذراندهاند، بسیار خسته شدهاند و سعی میکنند بازی حدسی بکنند اما در این هنگام دوباره مشکلی پیش میآید و آن این است که پشمک بازی حدسی را دوست ندارد و ممکن است به این دلیل بین او و چرزه تفرقه بیفتد و ...
در این بازی، چرزه یک عدد مانند \(x\) انتخاب میکند که عضو \(\left [ 1, n \right ]\) است ولی به پشمک نمیگوید! پشمک می تواند تعدادی عدد **در بازهی \(\left[1, n \right]\) **روی کاغذ بنویسد و در نهایت به چرزه بدهد. چرزه نیز پس از تحویل گرفتن کاغذ، تک تک روی تمام اعداد کاغذ دست میگذارد و ب.م.م \(x\) و آن عدد روی کاغذ را به پشمک میگوید. (چرزه هیچ وقت دروغ نمیگوید.) سپس پشمک باید عدد را با توجه به اطلاعات داده شده پیدا کند.
پشمک که اصلا از این بازی خوشش نیامده است، از شما میخواهد تا برنامهای برای او بنویسید تا با گرفتن عدد \(n\) حداقل تعداد عدد مورد نیاز برای نوشتن روی کاغذ و هم چنین این اعداد را به او بگویید. (وگرنه سفرشان همین جا پایان مییابد!)
تنها نکتهای که باید توجه کنید، این است که پشمک ابتدا تمام اعداد را مینویسد سپس چرزه جواب آنها را میدهد.
ورودی
در یک خط یک عدد \(n\) داده میشود که بدین معنا است که \(1 \leq x \leq n\).
\[1\leq n \leq 100\ 000\]
خروجی
در خط اول خروجی یک عدد \(t\)، که حداقل تعداد اعداد ممکن برای نوشتن روی کاغذ، برای آگاهی یافتن از عدد \(x\) است، نمایش داده شود.
در خط دوم نیز \(t\) عدد که اعداد مورد نیاز برای پرسش هستند را به ترتیب صعودی چاپ کنید. هم چنین توجه کنید که هر عدد خروجی باید خودش در بازهی \(\left [1, n \right]\) باشد.
مثال
ورودی نمونه ۱
6
خروجی نمونه ۱
3
3 4 5
ورودی نمونه ۲
2
خروجی نمونه ۲
1
2
توضیح:
در مثال اول با امتحان کردن، میتوان دید که پرسیدن دو عدد برای آگاهی یافتن از عدد \(x\) کافی نیست؛ برای مثال اگر فقط دو عدد \(\langle 3, 4\rangle \) را بنویسیم، نمیتوانیم عدد \(5\) را از عدد \(1\) تشخیص بدهیم.
برای اعداد \(1\)، \(2\)، \(3\)، \(4\)، \(5\) و \(6\) پاسخهای چرزه به \(\langle 3, 4, 5 \rangle \) به ترتیب برابر با \(\langle 1, 1, 1 \rangle\) ، \(\langle 1, 2, 1 \rangle\) ، \(\langle 3, 1, 1 \rangle\) ، \(\langle 1, 4, 1 \rangle\) ، \(\langle 1, 1, 5 \rangle\) و \(\langle 3, 2, 1 \rangle\) است که همان طور که میبینید، پاسخها برای هیچ دو عددی در بازهی \(1\) تا \(6\) یکسان نیست.