Problem
مکس در ایستگاه شروع قطار است و اکنون n نفر (از جمله خود مکس) می خواهند سوار آن شوند. آنها قبلاً به ترتیبی ردیف شده اند و هر یک از آنها کد منطقه ای
i را که به آنجا می روند می دانند.
رئیس قطار تعداد معینی از بخش های غیر متقاطع از دنباله اصلی افراد را انتخاب می کند (قطعات لازم نیست کل دنباله را پوشش دهند). افرادی که در همان بخش هستند در همان واگن قطار خواهند بود. سگمنت ها به گونه ای انتخاب می شوند که اگر حداقل یک نفر به شهر X رفت، همه افرادی که به شهر X می روند باید در یک ماشین باشند. این بدان معناست که آنها حق تعلق به بخش های مختلف را ندارند. لازم به ذکر است تمام افرادی که به شهر X می روند یا به آن شهر می روند و در یک ماشین هستند یا اصلاً جایی نمی روند.
راحتی سفر در قطار با افراد در سگمنت از l تا r برابر با XOR کدهای مختلف شهر برای افراد در سگمنت از l تا r است. عملیات XOR به عنوان OR انحصاری بیتی نیز شناخته می شود.
راحتی کلی بخش های انتخاب شده به عنوان مجموع راحتی هر بخش محاسبه می شود.
به Max کمک کنید تا حداکثر راحتی کلی را پیدا کند.
ورودی:
خط اول شامل یک عدد طبیعی n - تعداد افراد است.
خط دوم حاوی n عدد صحیح a
i (0 <= a
i <= 5000) است - کد شهری که شخص i به آن می رود.< br />
خروجی:
چاپ یک عدد صحیح - حداکثر راحتی کلی.
مثال:
<بدن>
| ورودی |
خروجی |
6
4 4 2 5 2 3
| 14 |
9
5 1 3 1 5 2 4 2 5
| 9 |