خیکوله پس از مدت‌ها ‎$n$‎ جفت جورابش را برای شست‌وشو درون ماشین لباس‌شویی قرار داد و بعد از اینکه شسته شدند، آن‌ها را در یک ردیف به ترتیب دل‌خواهی چید تا آن‌ها را جفت کند. با توجه به تعداد زیاد جوراب‌ها، او دستگاهی خریده است که قادر است با گرفتن یک بازه‌ی متوالی از جوراب‌ها، تعداد لنگه‌های متفاوت درون این بازه را اعلام کند. دو لنگه متفاوت هستند، اگر و فقط اگر متعلق به یک جفت نباشند. لازم به ذکر است این دستگاه هم‌اکنون در بازار موجود است و با نام تجاری ‎«جفت‌کن»‎ به شکل رایگان عرضه می‌شود اما برای هربار استفاده از این دستگاه لازم است ‎۱‎ تومان شارژ شود. خیکوله فقط ‎۱۳۰۰۰‎ تومان پول دارد‎!‎ برای همین باید با حداکثر ‎۱۳۰۰۰‎ بار استفاده از این دستگاه، کل جوراب‌ها را جفت‌بندی کند.

فرض کنید جوراب‌ها در یک ردیف چیده شده‌اند و از صفر تا ‎$2n-1$‎ شماره‌گذاری شده‌اند. شما باید تابع ‎joftkon(int n)‎ را بنویسید که با گرفتن تعداد اولیه‌ی جفت جوراب‌ها ‎($n$)‎ و استفاده از تابع sock_count(int s‎, ‎int e) (که همان دستگاه مذکور است)، جفت‌های متناظر را پیدا کند. توجه کنید که شما قادر به جابه‌جایی جوراب‌ها نیستید و فقط با استفاده از تابع ‎sock_count‎ باید جفت جوراب‌های متناظر را بیابید. در انتها باید جواب خود را با صدا زدن تابع ‎answer(int pairs[])‎ ارسال کنید. بنابراین آن‌ را فقط یک‌بار در انتهای برنامه‌تان صدا بزنید. جواب شما درون آرایه‌ای است که به این تابع ارسال می‌کنید. طول این آرایه باید ‎$2n$‎ باشد و در خانه‌ی ‎$i$‎ام آن باید شماره‌‌ی لنگه‌ی متناظر با جوراب ‎$i$‎ام را نوشته باشید.

در این سوال شما در صورتی نمره می‌گیرید که هم جوراب‌ها را به درستی جفت‌بندی کرده باشید و هم تعداد دفعات صدازدن تابع ‎sock_count(int s‎, ‎int e)‎ از ‎۱۳۰۰۰‎ بار بیشتر نباشد.

دقت کنید که شما نباید هیچ مقداری را از ورودی استاندارد بخوانید یا در خروجی استاندارد بنویسید، در غیر اینصورت ممکن است هیچ نمره‌ای نگیرید‎.‎

• int sock_count(int s‎, ‎int e)‎: این تابع در خروجی تعداد لنگه جوراب‌های متمایز از جوراب ‎$s$‎ام تا جوراب ‎$e$‎ام (شامل خود ‎$s$‎ و ‎($e$‎ را برمی‌گرداند. توجه کنید که جوراب‌ها از صفر تا ‎$2n-1$‎ شماره‌گذاری شده‌اند.
• void answer(int[] pairs): این تابع را برای ارسال جواب صدا بزنید. ورودی این تابع یک آرایه است که در خانه‌ی ‎$i$‎ام، شماره‌ی لنگه‌ی متناظر با آن جوراب نوشته شده است. این تابع را فقط یک‌بار صدا بزنید.

فرض کنید کلا ‎۲‎ جفت جوراب داریم که یکی از جفت‌ها در دو خانه‌ی اول و جفت دیگر در دو خانه‌ی آخر ردیف قرار دارد. در این صورت شما با پرسیدن سوال‌های زیر، جواب‌های داده شده را می‌گیرید:

• sock_count(0‎, ‎1) $\longrightarrow$ 1
• 2 $\longrightarrow$ sock_count(0‎, ‎3)‎
• 1 $\longrightarrow$ sock_count(2‎, ‎3)‎
• 2 $\longrightarrow$ sock_count(1‎, ‎3)‎

همچنین شما باید آرایه [1,0,3,2]‎ را به تابع ‎answer‎ بعنوان جواب پاس دهید.

یک بسته از فایل‌ها در فولدر ‎joftkon‎ در اختیار شما قرار گرفته است. این بسته شامل فایل‌های ‎Makefile‎، ‎joftkon.h‎، ‎joftkon.cpp‎ و grader.o‎ به همراه دو ورودی نمونه می‌باشد. تابع ‎int joftkon(int n)‎‌ درون فایل ‎joftkon.cpp‎ تعریف شده است که شما باید آن را پیاده‌سازی کنید. یک کد ساده که صرفا نحوه کار با توابع را به شما نشان می‌دهد درون این تابع نوشته شده است (که شما باید آن را تغییر دهید). کد خود را به صورت زیر کامپایل و اجرا کنید:

• ‎compile‎: ‎g+‎+ -‎O2‎ -‎Wall grader.o joftkon.cpp‎ -‎o joftkon or simply make
• ‎run‎: .‎/joftkon < grader.in.1‎

• شما برای تست برنامه خود می‌توانید با این ساختار ورودی تولید کنید. در خط اول ورودی عدد ‎$n$‎ را بدهید. در خط بعد ‎$2n$‎ عدد بدهید که عدد ‎$i$‎ ام شماره‌ی لنگه متناظر با جوراب ‎$i$‌‎ام می‌باشد (دقت کنید که شماره جوراب‌ها از ‎$0$‎ شروع می‌شود).

• ‎ تعداد جفت جوراب‌ها ‎($n$)‎ حداکثر ‎۱۰۰۰‎ است.
• ‎‎ برنامه‌ی شما باید حداکثر ‎۱۳۰۰۰‎ بار تابع ‎int sock_count(int s‎, ‎int e)‎ را صدا بزند.
• ‎‎ به ازای هر تست ترتیب جوراب‌ها از ابتدا مشخص می‌باشد و بسته به پرسش‌های شما تغییر نمی‌کند.
• ‎‎ اجرای برنامه‌ی شما نباید بیشتر از ‎۲‎ ثانیه طول بکشد. توابع int sock_count(int s‎, ‎int e)‎ و ‎void answer(int[] pairs)‎ روی هم رفته ‎۱‎ ثانیه بیشتر زمان برنامه‌ی شما را نمی‌گیرند‎.‎

خروجی این برنامه در صورتی که جواب درست با تعداد پرسش‌های مجاز به تابع ‎answer‎ داده شود Correct.‎ و در غیر اینصورت ‎Incorrect.‎ خواهد بود.

• زیرمساله‌ی اول ‎(۳۰ نمره) : در همه‌ی تست‌ها ‎$n\leq 100$‎.
• زیرمساله‌ی دوم ‎(۳۰‎ نمره): در همه‌ی تست‌ها ‎$n\leq 500$‎.
• زیرمساله‌ی سوم ‎(۴۰‎ نمره): در همه‌ی تست‌ها ‎$n\leq 1000$‎.

• سوال بعد