+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- روزی روزگاری $n$ تا از کامیون‌های شرکت باربری بمنثقتفخل بزرگراه امام علی (ع) را طی می‌کنند. همان‌طور که می‌دانید بزرگراه دارای $10^6$ ورودی و $10^6$ خروجی است به این صورت که ورودی $i$-ام روبه‌روی خروجی $i$-ام است. وقتی یک کامیون وارد بزرگراه می‌شود راننده آن یک بلیط سبز دریافت می‌کند که روی آن شماره آن ورودی و یک بلیط قرمز دریافت می‌کند که روی آن شماره خروجی که باید از آن خارج شود ثبت شده است. در هنگام خروج کامیون‌ها باید عوارض به مقدار اختلاف شماره دو عدد روی بلیط سبز و قرمز خود بپردازند. بمنثقتفخل راهی پیدا کرده است تا رانندگانش عوارض کمتری بپردازد.هر دو راننده می‌توانند یکدیگر را در بزرگراه ملاقات کنند و بلیط‌های قرمز خود را با هم عوض کنند، حتی اگر هم مسیر نباشند. به هر حال یک راننده نمی‌تواند از خروجی‌ای که از آن وارد بزرگراه شده است خارج شود زیرا این کار خیلی مشکوک است. شرکت باربری بمنثقتفخل از شما می‌خواهد برایش کمینه مجموع عوارضی که باید رانندگانش بپردازند را حساب کنید. # ورودی خط اول ورودی فقط شامل عدد $n$ است. در $n$ خط بعدی در هر خط دو عدد غیر برابر در بازه $1$ تا $10^6$ وجود دارد که به ترتیب شماره بلیط سبز و قرمز راننده $i$-ام است. هیچ دو راننده‌ای بلیط سبز برابر یا بلیط قرمز برابر ندارند. $$ 1 \le n \le 100\ 000$$ # زیرمسئله‎ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱| ۵ | $n\le 10$ | |۲| ۱۵ | $n \le 20$ | |۳| ۸۰ | بدون محدودیت اضافی | # خروجی خروجی برنامه تنها یک عدد است که برابر با کمینه مجموع عوارضی که باید رانندگان بمنثقتفخل بپردازند است. # مثال ## ورودی نمونه ۱ ``` 3 3 65 45 10 60 25 ``` ## خروجی نمونه ۱ ``` 32 ``` اگر راننده اول و سوم بلیط‌های قرمز خود را با هم عوض کنند سپس راننده دوم و سوم اینکار را انجام دهند. بعد از این کار بلیط قرمز رانندگان به ترتیب برابر ۱۰ و ۲۵ و ۶۵ می‌شود و مجموع عوارض پرداختی برابر $|65-60|+|25-45|+|10-3|=32$ می‌شود. ## ورودی نمونه ۲ ``` 3 5 5 6 7 8 8 ``` ## خروجی نمونه ۲ ``` 5 ```

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