• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۶۴ مگابایت

تیم مارکتینگ دیجی‌کال‍ا می‌خواهد در روز یلدا کمپینی را برگزار کند که در آن 2n2n آیتم را برای فروش ویژه قرار بدهد و به nn نفر اولی که از این آیتم‌ها خریداری کنند علاوه بر آیتمی که خریده‌اند، یک آیتم هدیه نیز تحویل بدهد. آیتم ها از 11 تا 2n2n شماره‌گذاری شده‌اند و هر شخص فقط می‌تواند یک کال‍ا را از این لیست برای خود بخرد.

شما شخصی هستید که قرار است یک لیست از nn آیتم خریداری شده تحویل بگیرید و nn جفت‌آیتم تحویل دهید به طوری که به هر شخص خریدار آیتمی که سفارش داده به علاوه یک آیتم هدیه تعلق گیرد.

حال دوستان شما چالشی برای شما مطرح می‌کنند که برای فهم آن ابتدا نیاز به یک تعریف دارید.

عدد خاص را اینگونه تعریف می‌کنیم:‌ تعداد جفت‌آیتم‌هایی که در آن‌ها شماره‌ی آیتم کاربر کم‌تر از شماره‌ی آیتم هدیه باشد. حال چالش شما این است که بعد از گرفتن لیست nn آیتم خریداری‌شده بگویید چند عدد خاص مختلف می‌توانید بسازید.

ورودی‌

خط اول شامل عدد cc است که تعداد کمپین‌ها را نشان می‌دهد. 1c10001 \leq c \leq 1000

خط اول هر کمپین عدد nn به عنوان تعداد سفارشات در کمپین به شما داده می‌شود.

1n200 0001 \leq n \leq 200 \ 000

خط دوم هر کمپین nn عدد مرتب‌شده از کوچک به بزرگ داده می‌شود. لازم به ذکر است جمع تمامی nnها از 200 000200 \ 000 بیشتر نمی‌شود.

خروجی‌

برای هر کمپین «تعداد» اعداد خاصی که می‌توانید بسازید را چاپ کنید.

مثال‌ها

ورودی نمونه

3
1
1
5
1 4 5 9 10
2
3 4
Plain text

خروجی نمونه

1
3
1
Plain text

در کمپین نخست این مثال، جمعا دو کالا موجود داریم (چون تعداد کالاها برابر 2n2n است). بنابراین تنها یک راه وجود دارد، آن هم اینکه به تنها کاربری که خرید کرده است، کالای شماره‌ی ۲ هدیه داده شود.

در کمپین دوم، سه حالت وجود دارد. عدد خاص برابر با ۲ باشد (برای مثال به ترتیب کالاهای ۲ و ۳ و ۶ و ۷ و ۸ به خریداران هدیه داده شوند)؛ یا می‌تواند برابر با ۳ باشد (به ترتیب کالاهای ۲ و ۶ و ۷ و ۳ و ۸ هدیه داده شوند)؛ یا می‌تواند برابر ۱ باشد (به ترتیب کالاهای ۸ و ۲ و ۳ و ۶ و ۷ هدیه داده شوند).

در کمپین سوم این مثال، در هر حال در هر جفت‌آیتمی که ایجاد کنیم شماره‌ی هدیه کم‌تر از شماره‌ی کالای خریداری‌شده است، بنابراین تنها عدد ۰ را داریم.


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.