+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون نهایی اول دوره ۲۶ المپیاد کامپیوتر ---------- پشمک و پارمیدا در پوستون زندگی می‌کنند. امسال در جشن سال نو، پشمک یک گردنبند به پارمیدا هدیه داده است. یک گردنبند در پوستون تعدادی مهره دارد که روی هر یک از مهره‌های آن‌ یک رقم بین $0$ تا $9$ نوشته شده است. بنابراین هر گردنبند، متناظر با یک عدد ‌صحیح نامنفی است که مهره‌های آن، از چپ به راست، رقم‌های آن عدد را، از پر ارزش‌ترین به کم‌ارزش‌ترین، نشان می‌دهند. دقت کنید که در چپ ترین مهره‌ی یک گردنبند تنها در حالتی امکان دارد رقم $0$ نوشته شده باشد که عدد متناظر با گردنبند، صفر باشد (یعنی گردنبند تنها یک مهره‌ با رقم $0$ داشته باشد) زیرا پر ارزش‌ترین رقم یک عدد بزرگتر از صفر، نمی‌تواند $0$ باشد. قیمت یک گردنبند که مهره‌های آن، به ترتیب از چپ به راست، $a_1, a_2, \ldots, a_n$ هستند، برابر تعداد نابجایی‌های دنباله‌ی مهره‌های آن است. به عبارت دیگر قیمت یک گردنبند، تعداد جفت‌های $(i, j)$ است که: + $i < j$ + $a_i > a_j$ دقت کنید در صورتی که دنباله‌ی مهره‌های یک گردنبند صعودی باشد، قیمت آن برابر با صفر خواهد بود. هم‌چنین هر چه عدد متناظر با یک گردنبند کوچکتر باشد، آن گردنبند جذاب‌تر خواهد بود. برای مثال، جذاب‌ترین گردنبند گردنبندی است که عدد متناظر با آن برابر با صفر باشد. به ازای هر عدد صحیح نامنفی، دقیقاً یک گردنبند در پوستون وجود دارد که متناظر با این عدد است. پارمیدا، از روی کنجکاوی می‌خواهد تعداد گردنبندهای جذاب‌تر و با قیمت کمتر از گردنبدی که هدیه گرفته است را بشمارد. برنامه‌ای بنویسید که این عدد را محاسبه کند. # ورودی در خط اول ورودی $n$، عدد متناظر با گردنبندی که پشمک به پارمیدا هدیه داده است، آمده است. $$1 \le n \le 10^{18}$$ # خروجی در تنها خط خروجی، تعداد گردنبندهای جذاب‌تر و با قیمت کمتر از گردنبند پارمیدا را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۷ | $n \le 100\ 000$ | | ۲ | ۴۳ | $n \le 10^{12}$ | | ۳ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 123 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 1991 ``` ## خروجی نمونه ۲ ``` 999 ``` ## ورودی نمونه ۳ ``` 100000 ``` ## خروجی نمونه ۳ ``` 50248 ```