- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شهر اعداد که پیشتر شورای شهر خود را تشکیل داده بود، به ناکارآمدی شورا حتی اگر همهشان کارا باشند پیبرد. مردم شهر اینک نیاز به پادشاه را درک کردهاند و تصمیم به انتخاب پادشاه میگیرند.
اما مشکل اینجاست که مردم نظر یکسانی درباره فرد شایسته ندارند. به طور دقیقتر هر فردی در شهر اعداد یک عدد دارد و از نظر فردی با عدد \(x\) فردی با عدد \(y\) بهتر از فردی با عدد \(z\) است اگر و تنها اگر \(y \oplus x > z \oplus x\) باشد. که در اینجا منظور از علامت \(\oplus\) عملیات xor است.
حال اعداد شهروندان شهر به شما داده میشود و بگویید در همه حالات انتخاب دو نفر و یک داور، هر شهروند چند بار پیروز میشود. توجه کنید داور میتواند شرکت کننده هم باشد.
برای درک بهتر میتوانید به توضیحات نمونه مراجعه کنید.
ورودی
در سطر اول \(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
توضیح نمونه ۱
\[ [(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 \]
ورودی نمونه ۲
5
0 0 1 4 5
خروجی نمونه ۲
6 6 10 11 12