+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- استاد که به تازگی از سفر فرنگ بازگشته، هنوز به زبان فارسی عادت نکرده‌است. بنابراین، به مناسبت بازگشت خود، یک سرمونی (ceremony) ترتیب داده‌است. استاد $n$ نفر را به سرمونی خود دعوت کرده و آن‌ها را با شماره‌های $1$ تا $n$ شماره‌گذاری کرده‌است. هر یک از این $n$ نفر یک کفش چپ و یک کفش راست دارد. جاکفشی خانه‌ی استاد یک نوار بزرگ شامل $10^9$ خانه است که با شماره‌های $1$ تا $10^9$ شماره‌گذاری شده‌اند. می‌دانیم در ابتدا مهمان $i$-ام کفش چپ خود را در خانه‌ی $L_i$ جاکفشی و کفش راست خود را در خانه‌ی $R_i$ آن قرار داده‌است. تضمین شده که هیچ دو کفشی در یک خانه قرار ندارند. دوست استاد که می‌خواهد مهمان‌ها موقع خروج از مهمانی دچار مشکل نشوند، دوست دارد که کفش چپ هر مهمان در خانه‌ی سمت چپ (بلافاصله‌ی) کفش سمت راست او باشد. به عبارت دیگر، دوست دارد که اگر در وضعیت نهایی، کفش سمت راست در خانه‌ی $x$ است، کفش سمت چپ در خانه‌ی $x-1$ باشد. برای رسیدن به این وضعیت، او در هر عملیات می‌تواند دو خانه‌ی مجاور جاکفشی را انتخاب کرده و محتوای آن دو را با هم جابه‌جا کند. به دوست استاد کمک کنید و کمینه‌ی تعداد عملیات‌ها برای رساندن جاکفشی به وضعیت مطلوب را چاپ کنید. # ورودی در خط اول ورودی عدد صحیح $t$ ($1 \le t \le 10^5$) که برابر تعداد سناریوها است، می‌آید. در خط اول هر سناریو، عدد صحیح $n$ ($1 \le n \le 5 \times 10^5$) که نشان‌دهنده‌ی تعداد مهمان‌های سرمونی‌است، می‌آید. در هر یک از $n$ خط بعدی سناریو، دو عدد $L_i$ و $R_i$ ($1 \le L_i, R_i \le 10^9\,$) که به ترتیب نشان‌دهنده‌ی جایگاه‌های قرارگیری کفش چپ و راست مهمان $i$ـم‌اند، می‌آیند. تضمین می‌شود که مجموع $n$ها در همه‌ی سناریوها حداکثر $5 \times 10^5$ است. # خروجی برای هر سناریو، کمینه‌ی تعداد عملیات‌ها برای رسیدن به وضعیت مطلوب را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 1 6 5 2 3 4 2 1 9 2 10 1 1000000000 1 ``` ## خروجی نمونه ۱ ``` 7 13 999999999 ``` یک دنباله عملیات ممکن که در کمترین مرحله دوست می‌تواند با آن کفش‌ها را مرتب کند: | جایگاه ۶ | جایگاه ۵ | جایگاه ۴ | جایگاه ۳ | جایگاه ۲ | جایگاه ۱ | گام‌ها | |:---:|:---:|:---:|:---:|:---:|:---:|:---:| |R1|L2|R3|L3|R2|L1|0| |R1|L2|R3|L3|**L1**|**R2**|1| |R1|**R3**|**L2**|L3|L1|R2|2| |R1|R3|**L3**|**L2**|L1|R2|3| |R1|R3|L3|**L1**|**L2**|R2|4| |**R3**|**R1**|L3|L1|L2|R2|5| |R3|**L3**|**R1**|L1|L2|R2|6| |R3|L3|R1|L1|**R2**|**L2**|7|

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