- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
تیم مارکتینگ دیجیکالا میخواهد در روز یلدا کمپینی را برگزار کند که در آن \(2n\) آیتم را برای فروش ویژه قرار بدهد و به \(n\) نفر اولی که از این آیتمها خریداری کنند علاوه بر آیتمی که خریدهاند، یک آیتم هدیه نیز تحویل بدهد. آیتم ها از \(1\) تا \(2n\) شمارهگذاری شدهاند و هر شخص فقط میتواند یک کالا را از این لیست برای خود بخرد.
شما شخصی هستید که قرار است یک لیست از \(n\) آیتم خریداری شده تحویل بگیرید و \(n\) جفتآیتم تحویل دهید به طوری که به هر شخص خریدار آیتمی که سفارش داده به علاوه یک آیتم هدیه تعلق گیرد.
حال دوستان شما چالشی برای شما مطرح میکنند که برای فهم آن ابتدا نیاز به یک تعریف دارید.
عدد خاص را اینگونه تعریف میکنیم: تعداد جفتآیتمهایی که در آنها شمارهی آیتم کاربر کمتر از شمارهی آیتم هدیه باشد. حال چالش شما این است که بعد از گرفتن لیست \(n\) آیتم خریداریشده بگویید چند عدد خاص مختلف میتوانید بسازید.
ورودی
خط اول شامل عدد \(c\) است که تعداد کمپینها را نشان میدهد. \[1 \leq c \leq 1000\]
خط اول هر کمپین عدد \(n\) به عنوان تعداد سفارشات در کمپین به شما داده میشود.
\[1 \leq n \leq 200 \ 000\]
خط دوم هر کمپین \(n\) عدد مرتبشده از کوچک به بزرگ داده میشود. لازم به ذکر است جمع تمامی \(n\)ها از \(200 \ 000\) بیشتر نمیشود.
خروجی
برای هر کمپین «تعداد» اعداد خاصی که میتوانید بسازید را چاپ کنید.
مثالها
ورودی نمونه
3
1
1
5
1 4 5 9 10
2
3 4
خروجی نمونه
1
3
1
در کمپین نخست این مثال، جمعا دو کالا موجود داریم (چون تعداد کالاها برابر \(2n\) است). بنابراین تنها یک راه وجود دارد، آن هم اینکه به تنها کاربری که خرید کرده است، کالای شمارهی ۲ هدیه داده شود.
در کمپین دوم، سه حالت وجود دارد. عدد خاص برابر با ۲ باشد (برای مثال به ترتیب کالاهای ۲ و ۳ و ۶ و ۷ و ۸ به خریداران هدیه داده شوند)؛ یا میتواند برابر با ۳ باشد (به ترتیب کالاهای ۲ و ۶ و ۷ و ۳ و ۸ هدیه داده شوند)؛ یا میتواند برابر ۱ باشد (به ترتیب کالاهای ۸ و ۲ و ۳ و ۶ و ۷ هدیه داده شوند).
در کمپین سوم این مثال، در هر حال در هر جفتآیتمی که ایجاد کنیم شمارهی هدیه کمتر از شمارهی کالای خریداریشده است، بنابراین تنها عدد ۰ را داریم.