문제
민찬이는 KSA 학생들을 위해 1ドル$번부터 $N$번까지의 문제들로 구성된 문제 목록을 준비했다. $i$번 문제의 레벨은 $A_i$이다.
학생들로부터 문제가 너무 많다는 불평을 들은 민찬이는 문제 목록을 한 개 이상의 연속된 구간으로 분할해, 구간마다 그 구간에 속한 문제들을 하나의 새로운 문제로 대체하려고 한다. 단, 각 구간에는 적어도 하나의 문제가 포함되어 있어야 하며, KSA 학생들을 더 헷갈리게 하기 위해 인접한 두 구간의 문제 수는 서로 다르도록 분할해야 한다.
새로운 문제의 레벨은 해당하는 구간에 속한 문제의 레벨을 모두 bitwise XOR한 값이다. 민찬이는 KSA 학생들의 실력 향상을 위해 새로운 문제들의 레벨 합을 최대로 하려고 한다. 문제 목록을 적절한 구간들로 분할했을 때, 새로운 문제들의 레벨 합의 최댓값을 구해보자.
출력
새로운 문제들의 레벨 합의 최댓값을 출력한다.
제한
- 1ドル \leq N \leq 2 \times 10^5$
- 0ドル \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 23 | $N \le 100$
|
| 2 | 36 | $N \le 3000$
|
| 3 | 41 | 추가 제약 조건 없음
|
$[1, 2],ドル $[3, 3]$ 두 구간으로 분할하면 레벨 합을 8ドル$로 만들 수 있다.
$(5 \oplus 3) + (2) = 8$
$[1, 1],ドル $[2, 3],ドル $[4, 4]$ 세 구간으로 분할하면 레벨 합을 18ドル$로 만들 수 있다.
$(6) + (2 \oplus 4) + (6) = 18$
$[1, 4]$ 한 구간으로 분할하면 레벨 합을 15ドル$로 만들 수 있다.
$(1 \oplus 2 \oplus 4 \oplus 8)= 15$
노트
음이 아닌 두 정수 $A$와 $B$의 bitwise XOR, 즉 $A \oplus B$는 다음과 같이 정의된다:
- $A \oplus B$를 이진수로 나타냈을때 2ドル^k$의 자리 숫자($k \geq 0$)는 $A$와 $B$에서 그 자리에 있는 숫자 중 정확히 하나가 1ドル$이면 1ドル$이고, 그렇지 않다면 0ドル$이다.
예를 들어, 3ドル \oplus 5 = 6$이다. (이진수로 나타내면: 011ドル \oplus 101 = 110$).
W3sicHJvYmxlbV9pZCI6IjI5MjAwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYjM4XHVjODFjIFx1YzIxOCBcdWM5MDRcdWM3NzRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1Y2MyY1x1Yzc3NFx1YjI5NCBLU0EgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NCAkMSRcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmIzOFx1YzgxY1x1YjRlNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1ODhcdWIyZTQuICRpJFx1YmM4OCBcdWJiMzhcdWM4MWNcdWM3NTggXHViODA4XHViY2E4XHVjNzQwICRBX2kkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWI4NWNcdWJkODBcdWQxMzAgXHViYjM4XHVjODFjXHVhYzAwIFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWIyZTRcdWIyOTQgXHViZDg4XHVkM2M5XHVjNzQ0IFx1YjRlNFx1Yzc0MCBcdWJiZmNcdWNjMmNcdWM3NzRcdWIyOTQgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVhZDZjXHVhYzA0XHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU3NCwgXHVhZDZjXHVhYzA0XHViOWM4XHViMmU0IFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YmIzOFx1YzgxY1x1YjRlNFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMGM4XHViODVjXHVjNmI0IFx1YmIzOFx1YzgxY1x1Yjg1YyBcdWIzMDBcdWNjYjRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YWMwMSBcdWFkNmNcdWFjMDRcdWM1ZDBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIEtTQSBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMzU0IFx1ZDVmN1x1YWMwOFx1YjlhY1x1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YmIzOFx1YzgxYyBcdWMyMThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjNjNFx1Yjg1ZCBcdWJkODRcdWQ1NjBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzhcdWI4NWNcdWM2YjQgXHViYjM4XHVjODFjXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc0MCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NTggXHViODA4XHViY2E4XHVjNzQ0IFx1YmFhOFx1YjQ1MCBiaXR3aXNlIFhPUlx1ZDU1YyBcdWFjMTJcdWM3NzRcdWIyZTQuIFx1YmJmY1x1Y2MyY1x1Yzc3NFx1YjI5NCBLU0EgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YzJlNFx1YjgyNSBcdWQ1YTVcdWMwYzFcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM4MWNcdWI0ZTRcdWM3NTggXHViODA4XHViY2E4IFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVhZDZjXHVhYzA0XHViNGU0XHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM4MWNcdWI0ZTRcdWM3NTggXHViODA4XHViY2E4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM4MWNcdWI0ZTRcdWM3NTggXHViODA4XHViY2E4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YjQ1MCBcdWM4MTVcdWMyMTggJEEkXHVjNjQwICRCJFx1Yzc1OCBiaXR3aXNlIFhPUiwgXHVjOTg5ICRBIFxcb3BsdXMgQiRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JEEgXFxvcGx1cyBCJFx1Yjk3YyBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHVjNzQ0XHViNTRjICQyXmskXHVjNzU4IFx1Yzc5MFx1YjlhYyBcdWMyMmJcdWM3OTAoJGsgXFxnZXEgMCQpXHViMjk0ICRBJFx1YzY0MCAkQiRcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwIFx1YzkxMSBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTU4XHViMDk4XHVhYzAwICQxJFx1Yzc3NFx1YmE3NCAkMSRcdWM3NzRcdWFjZTAsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgJDAkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICQzIFxcb3BsdXMgNSA9IDYkXHVjNzc0XHViMmU0LiAoXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NDogJDAxMSBcXG9wbHVzIDEwMSA9IDExMCQpLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxIFxcbGVxIE4gXFxsZXEgMiBcXHRpbWVzIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQwIFxcbGVxIEFfaSBcXGxlcSAxMF45JCAkKDEgXFxsZXEgaSBcXGxlcSBOKSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE4gXFxsZSAxMDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlIDMwMDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+JFsxLCAyXSQsICRbMywgM10kIFx1YjQ1MCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHVkNTU4XHViYTc0IFx1YjgwOFx1YmNhOCBcdWQ1NjlcdWM3NDQgJDgkXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4kKDUgXFxvcGx1cyAzKSArICgyKSA9IDgkPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPiRbMSwgMV0kLCAkWzIsIDNdJCwgJFs0LCA0XSQgXHVjMTM4Jm5ic3A7XHVhZDZjXHVhYzA0XHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU1OFx1YmE3NCBcdWI4MDhcdWJjYTggXHVkNTY5XHVjNzQ0ICQxOCRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiQoNikgKyAoMiBcXG9wbHVzIDQpICsgKDYpID0gMTgkPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPiRbMSwgNF0kIFx1ZDU1YyZuYnNwO1x1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWQ1NThcdWJhNzQgXHViODA4XHViY2E4IFx1ZDU2OVx1Yzc0NCAkMTUkXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4kKDEgXFxvcGx1cyAyIFxcb3BsdXMgNCBcXG9wbHVzIDgpPSAxNSQ8XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyOTIwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlZHVjaW5nIHRoZSBOdW1iZXIgb2YgUHJvYmxlbXMiLCJkZXNjcmlwdGlvbiI6IjxwPk1pbmNoYW4gaGFzIHByZXBhcmVkIGEgbGlzdCBvZiBwcm9ibGVtcyBmb3IgS1NBIHN0dWRlbnRzLCBjb25zaXN0aW5nIG9mIHByb2JsZW1zIG51bWJlcmVkIGZyb20gJDEkIHRvICROJC4gVGhlIGxldmVsIG9mIHByb2JsZW0gJGkkIGlzICRBX2kkLjxcL3A+XHJcblxyXG48cD5BZnRlciByZWNlaXZpbmcgY29tcGxhaW50cyBmcm9tIHRoZSBzdHVkZW50cyBhYm91dCBoYXZpbmcgdG9vIG1hbnkgcHJvYmxlbXMsIE1pbmNoYW4gd2FudHMgdG8gZGl2aWRlIHRoZSBwcm9ibGVtIGxpc3QgaW50byBvbmUgb3IgbW9yZSBjb25zZWN1dGl2ZSBzZWdtZW50cyBhbmQgcmVwbGFjZSBlYWNoIHNlZ21lbnQgd2l0aCBhIG5ldyBwcm9ibGVtLiBIb3dldmVyLCBlYWNoIHNlZ21lbnQgbXVzdCBjb250YWluIGF0IGxlYXN0IG9uZSBwcm9ibGVtLCBhbmQgYWRqYWNlbnQgc2VnbWVudHMgbXVzdCBoYXZlIGRpZmZlcmVudCBudW1iZXJzIG9mIHByb2JsZW1zIHRvIGNvbmZ1c2UgdGhlIEtTQSBzdHVkZW50cy48XC9wPlxyXG5cclxuPHA+VGhlIGxldmVsIG9mIHRoZSBuZXcgcHJvYmxlbSBpcyB0aGUgYml0d2lzZSBYT1Igb2YgdGhlIGxldmVscyBvZiB0aGUgcHJvYmxlbXMgaW4gdGhlIGNvcnJlc3BvbmRpbmcgc2VnbWVudC4gTWluY2hhbiB3YW50cyB0byBtYXhpbWl6ZSB0aGUgc3VtIG9mIHRoZSBsZXZlbHMgb2YgdGhlIG5ldyBwcm9ibGVtcyBmb3IgdGhlIGltcHJvdmVtZW50IG9mIHRoZSBLU0Egc3R1ZGVudHMmIzM5OyBza2lsbHMuIExldCYjMzk7cyBmaW5kIHRoZSBtYXhpbXVtIHBvc3NpYmxlIHN1bSBvZiB0aGUgbGV2ZWxzIG9mIHRoZSBuZXcgcHJvYmxlbXMgd2hlbiBkaXZpZGluZyB0aGUgcHJvYmxlbSBsaXN0IGludG8gYXBwcm9wcmlhdGUgc2VnbWVudHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtYXhpbXVtIHBvc3NpYmxlIHN1bSBvZiB0aGUgbGV2ZWxzIG9mIHRoZSBuZXcgcHJvYmxlbXMuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBiaXR3aXNlIFhPUiBvZiBub24tbmVnYXRpdmUgaW50ZWdlcnMgJEEkIGFuZCAkQiQsICRBIFxcb3BsdXMgQiQsIGlzIGRlZmluZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5XaGVuICRBIFxcb3BsdXMgQiQgaXMgd3JpdHRlbiBpbiBiYXNlIHR3bywgdGhlIGRpZ2l0IGluIHRoZSAkMl5rJCYjMzk7cyBwbGFjZSQoayBcXGdlcSAwKSQgaXMgMSBpZiBleGFjdGx5IG9uZSBvZiB0aGUgZGlnaXRzIGluIHRoYXQgcGxhY2Ugb2YgJEEkIGFuZCAkQiQgaXMgJDEkLCBhbmQgJDAkIG90aGVyd2lzZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB3ZSBoYXZlICQzIFxcb3BsdXMgNSA9IDYkIChpbiBiYXNlIHR3bzogJDAxMSBcXG9wbHVzIDEwMSA9IDExMCQpLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBOIFxcbGVxIDIgXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlcSBBX2kgXFxsZXEgMTBeOSQgJCgxIFxcbGVxIGkgXFxsZXEgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgMTAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSAzMDAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50czxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5JZiB5b3UgZGl2aWRlIHRoZSBhcnJheSBpbnRvIHR3byZuYnNwO3NlZ21lbnRzJm5ic3A7JFsxLCAyXSQgYW5kJm5ic3A7JFszLCAzXSQsIHRoZSZuYnNwO3N1bSBvZiB0aGUgbGV2ZWxzIG9mIHRoZSBuZXcgcHJvYmxlbXMgaXMmbmJzcDskOCQuPFwvcD5cclxuXHJcbjxwPiQoNSBcXG9wbHVzIDMpICsgKDIpID0gOCQ8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+SWYgeW91IGRpdmlkZSB0aGUgYXJyYXkgaW50byB0aHJlZSBzZWdtZW50cyZuYnNwOyRbMSwgMV0kLCAkWzIsIDNdJCBhbmQmbmJzcDskWzQsIDRdJCwgdGhlJm5ic3A7c3VtIG9mIHRoZSBsZXZlbHMgb2YgdGhlIG5ldyBwcm9ibGVtcyBpcyZuYnNwOyQxOCQuPFwvcD5cclxuXHJcbjxwPiQoNikgKyAoMiBcXG9wbHVzIDQpICsgKDYpID0gMTgkPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPklmIHlvdSBkaXZpZGUgdGhlIGFycmF5IGludG8gb25lIHNlZ21lbnQmbmJzcDskWzEsIDRdJCwgdGhlJm5ic3A7c3VtIG9mIHRoZSBsZXZlbHMgb2YgdGhlIG5ldyBwcm9ibGVtcyBpcyZuYnNwOyQxNSQuPFwvcD5cclxuXHJcbjxwPiQoMSBcXG9wbHVzIDIgXFxvcGx1cyA0IFxcb3BsdXMgOCk9IDE1JDxcL3A+XHJcbiJ9XQ==