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

شهر اعداد که پیشتر شورای شهر خود را تشکیل داده بود، به ناکارآمدی شورا حتی اگر همه‌شان کارا باشند پی‌برد. مردم شهر اینک نیاز به پادشاه را درک کرده‌اند و تصمیم به انتخاب پادشاه می‌گیرند.

اما مشکل اینجاست که مردم نظر یکسانی درباره فرد شایسته ندارند. به طور دقیق‌تر هر فردی در شهر اعداد یک عدد دارد و از نظر فردی با عدد xx فردی با عدد yy بهتر از فردی با عدد zz است اگر و تنها اگر yx>zxy \oplus x > z \oplus x باشد. که در اینجا منظور از علامت \oplus عملیات xor است.

حال اعداد شهروندان شهر به شما داده می‌شود و بگویید در همه حالات انتخاب دو نفر و یک داور، هر شهروند چند بار پیروز می‌شود. توجه کنید داور می‌تواند شرکت کننده هم باشد.

برای درک بهتر می‌توانید به توضیحات نمونه مراجعه کنید.

ورودی

در سطر اول nn تعداد شهروندان می‌آید. در سطر بعد nn عدد می‌آید که iiامین آن‌ها aia_i عدد شهروند ii است. 1n1000,000 1 \le n \le 1000 , 000 0ai1090 \le a_i \le 10^9

خروجی

در تنها سطر خروجی تعداد برتری های افراد با فاصله مطلوب است.

مثال

ورودی نمونه ۱

3
0 2 3
Plain text

خروجی نمونه ۱

4 2 3
Plain text

توضیح نمونه ۱

[(0,2),0]:00<20,winner: 2 [(0,2), 0]: 0 \oplus 0 < 2 \oplus 0, winner:\space 2 [(0,3),0]:00<30,winner: 3 [(0,3), 0]: 0 \oplus 0 < 3 \oplus 0, winner:\space 3 [(2,3),0]:20<30,winner: 3 [(2,3), 0]: 2 \oplus 0 < 3 \oplus 0, winner:\space 3 [(0,2),2]:02>22,winner: 0 [(0,2), 2]: 0 \oplus 2 > 2 \oplus 2, winner:\space 0 [(0,3),2]:02>32,winner: 0 [(0,3), 2]: 0 \oplus 2 > 3 \oplus 2, winner:\space 0 [(2,3),2]:22<32,winner: 3 [(2,3), 2]: 2 \oplus 2 < 3 \oplus 2, winner:\space 3 [(0,2),3]:03>23,winner: 0 [(0,2), 3]: 0 \oplus 3 > 2 \oplus 3, winner:\space 0 [(0,3),3]:03<33,winner: 0 [(0,3), 3]: 0 \oplus 3 < 3 \oplus 3, winner:\space 0 [(2,3),3]:23>33,winner: 2 [(2,3), 3]: 2 \oplus 3 > 3 \oplus 3, winner:\space 2

ورودی نمونه ۲

5
0 0 1 4 5
Plain text

خروجی نمونه ۲

6 6 10 11 12
Plain text

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