+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شهر اعداد که پیشتر شورای شهر خود را تشکیل داده بود، به ناکارآمدی شورا حتی اگر همه‌شان **کارا** باشند پی‌برد. مردم شهر اینک نیاز به پادشاه را درک کرده‌اند و تصمیم به انتخاب پادشاه می‌گیرند. اما مشکل اینجاست که مردم نظر یکسانی درباره فرد شایسته ندارند. به طور دقیق‌تر هر فردی در شهر اعداد یک عدد دارد و از نظر فردی با عدد $x$ فردی با عدد $y$ بهتر از فردی با عدد $z$ است اگر و تنها اگر $y \oplus x > z \oplus x$ باشد. که در اینجا منظور از علامت $\oplus$ عملیات [**xor**](https://fa.wikipedia.org/wiki/%DB%8C%D8%A7%DB%8C_%D8%A7%D9%86%D8%AD%D8%B5%D8%A7%D8%B1%DB%8C) است. حال اعداد شهروندان شهر به شما داده می‌شود و بگویید در همه حالات **انتخاب** دو نفر و یک داور، هر شهروند چند بار پیروز می‌شود. **توجه کنید داور می‌تواند شرکت کننده هم باشد.** برای درک بهتر می‌توانید به توضیحات نمونه مراجعه کنید. # ورودی در سطر اول $n$ تعداد شهروندان می‌آید. در سطر بعد $n$ عدد می‌آید که $i$امین آن‌ها $a_i$ عدد شهروند $i$ است. $$ 1 \le n \le 1000 \, 000$$ $$0 \le a_i \le 10^9$$ # خروجی در تنها سطر خروجی تعداد برتری های افراد با فاصله مطلوب است. # مثال ## ورودی نمونه ۱ ``` 3 0 2 3 ``` ## خروجی نمونه ۱ ``` 4 2 3 ``` <details class="blue"> <summary> توضیح نمونه ۱ </summary> $$ [(0,2), 0]: 0 \oplus 0 < 2 \oplus 0, winner:\space 2 $$ $$ [(0,3), 0]: 0 \oplus 0 < 3 \oplus 0, winner:\space 3 $$$$ [(2,3), 0]: 2 \oplus 0 < 3 \oplus 0, winner:\space 3 $$$$ [(0,2), 2]: 0 \oplus 2 > 2 \oplus 2, winner:\space 0 $$$$ [(0,3), 2]: 0 \oplus 2 > 3 \oplus 2, winner:\space 0 $$$$ [(2,3), 2]: 2 \oplus 2 < 3 \oplus 2, winner:\space 3 $$$$ [(0,2), 3]: 0 \oplus 3 > 2 \oplus 3, winner:\space 0 $$$$ [(0,3), 3]: 0 \oplus 3 < 3 \oplus 3, winner:\space 0 $$$$ [(2,3), 3]: 2 \oplus 3 > 3 \oplus 3, winner:\space 2 $$ </details> ## ورودی نمونه ۲ ``` 5 0 0 1 4 5 ``` ## خروجی نمونه ۲ ``` 6 6 10 11 12 ```

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