پیراهن


صبح برای آماده شدن پیراهنی پوشیده‌ایم که n+1n+1 دکمه دارد. اول از همه دکمه‌ی اول و آخرش را می‌بندیم. از آن‌جایی که خیلی عجله داریم، همین‌طوری از خانه بیرون می‌رویم و بین راه بقیه‌ی دکمه‌ها را می‌بندیم. هر طولی از پیراهن (بین دو دکمه) که دکمه‌هایش بسته نشده باشند، در هر دقیقه «زشتی»‌ای ایجاد می‌کنند که برابر است با توان دوم آن طول منهای یک. یعنی اول کار زشتی پیراهن n21n^2-1 (مثلاً اگر ۱۱تا دکمه داشته باشیم و فقط اولی و آخری بسته باشند، زشتی این بازه می‌شود ۹۹ در هر دقیقه). ما در هر دقیقه می‌توانیم یک دکمه را ببندیم. می‌خواهیم به ترتیبی دکمه‌ها را ببندیم که مجموعِ زشتیِ نمای پیراهنمان تا وقتی که همه‌ی دکمه‌ها بسته شوند کم‌ترین مقدار ممکن باشد.

ورودی🔗

عدد طبیعی n<1000n<1000 (که یکی کم‌تر از تعداد دکمه‌هاست).

خروجی🔗

یک عدد طبیعی که حداقل مجموع زشتی ممکن است.

ورودی نمونه🔗

6
Plain text

خروجی نمونه🔗

71
Plain text