아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

산타 춘배의 선물 나눠주기

시간 제한1초메모리 제한1024 MB

요약
가격이 0에서 3인 선물 N개를 N/2쌍으로 묶어 각 쌍 XOR 값의 합이 최대가 되도록 한다.
난이도

보통10점 중 5점

유형
그리디, 수학, 비트 연산, 조합론
정답자
아직 제출이 없습니다

문제

산타 춘배

산타 춘배는 아기 고양이들에게 나눠줄 선물을 정리하고 있다. 총 NN개의 선물을 N2\frac{N}{2}마리의 아기 고양이들에게 2개씩 나누어 주려고 한다. 여기서 NN은 짝수이다.

NN개의 상품은 각각 가격이 있고, 이 가격은 00 이상 33 이하의 정수이다. 한 아기 고양이가 선물을 받을 때 얻는 만족도는, 받은 선물 2개의 가격을 XOR한 값이다. 예를 들어 선물 2개의 가격이 각각 11, 22라면 만족도는 11 XOR 2=32 = 3이고, 선물 2개의 가격이 각각 33, 33이라면 만족도는 33 XOR 3=03 = 0이다.

산타 춘배는 아기 고양이들에게 어떻게 선물을 나눠주어야 만족도 총합이 최대가 될지 고민 중이다. 춘배를 위해 이를 계산하는 프로그램을 만들어 주자!

입력

첫 번째 줄에 춘배가 가지고 있는 선물의 개수 NN이 주어진다. (2≤N≤200,000, N(2 \le N \le 200\\,000,\ N은 짝수))

두 번째 줄에 선물 NN개의 가격이 공백으로 구분되어 주어진다. 상품의 가격은 모두 00 이상 33 이하의 정수이다.

출력

산타 춘배가 아기 고양이들에게 선물을 나눠줬을 때 얻을 수 있는 만족도의 최댓값을 출력하라.

힌트

XOR의 정의는 여기에서 확인할 수 있다.

예제2

  1. 예제 1

    입력
    6
    0 1 2 3 2 3
    
    예상 출력
    7
    
  2. 예제 2

    입력
    2
    3 3
    
    예상 출력
    0