{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:\u003c/p\u003e\u003cp\u003eVladik is at initial train station, and now \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e people (including Vladik) want to get on the train. They are already lined up in some order, and for each of them the city code \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is known (the code of the city in which they are going to).\u003c/p\u003e\u003cp\u003eTrain chief selects some number of disjoint segments of the original sequence of people (covering entire sequence by segments is \u003cspan class\u003d\"tex-font-style-bf\"\u003enot necessary\u003c/span\u003e). People who are in the same segment will be in the same train carriage. The segments are selected in such way that if at least one person travels to the city \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, then all people who are going to city \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e should be in the same railway carriage. This means that they can’t belong to different segments. Note, that all people who travel to the city \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, either go to it and in the same railway carriage, or do not go anywhere at all.\u003c/p\u003e\u003cp\u003eComfort of a train trip with people on segment from position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e to position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e is equal to \u003cspan class\u003d\"tex-font-style-tt\"\u003eXOR\u003c/span\u003e of all distinct codes of cities for people on the segment from position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e to position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e. \u003cspan class\u003d\"tex-font-style-tt\"\u003eXOR\u003c/span\u003e operation also known as exclusive \u003cspan class\u003d\"tex-font-style-tt\"\u003eOR\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTotal comfort of a train trip is equal to sum of comfort for each segment.\u003c/p\u003e\u003cp\u003eHelp Vladik to know maximal possible total comfort.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst line contains single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000\u003c/span\u003e)\u0026nbsp;— number of people.\u003c/p\u003e\u003cp\u003eSecond line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 5000\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e denotes code of the city to which \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th person is going.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output should contain a single integer\u0026nbsp;— maximal possible total comfort.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n4 4 2 5 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\n5 1 3 1 5 2 4 2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case best partition into segments is: \u003cspan class\u003d\"tex-span\"\u003e[4, 4]\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e[2, 5, 2]\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e[3]\u003c/span\u003e, answer is calculated as follows: \u003cspan class\u003d\"tex-span\"\u003e4 + (2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003exor\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e5) + 3 \u003d 4 + 7 + 3 \u003d 14\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIn the second test case best partition into segments is: \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e[3]\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e[2, 4, 2]\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, answer calculated as follows: \u003cspan class\u003d\"tex-span\"\u003e3 + (2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003exor\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e4) \u003d 3 + 6 \u003d 9\u003c/span\u003e.\u003c/p\u003e"}}]}