산타 춘배의 선물 나눠주기

면접 대비

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

요약

가격이 0부터 3까지인 선물 N개를 두 개씩 짝지어 N/2쌍을 만들 때, 각 쌍의 XOR 값을 모두 더한 합의 최댓값을 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 구현
정답자: 아직 제출이 없습니다

문제

산타 춘배

산타 춘배는 아기 고양이들에게 나눠줄 선물을 정리하고 있다. 선물은 총 $N$ 개이고, 춘배는 이를 2개씩 묶어 $\frac{N}{2}$ 마리의 아기 고양이에게 준다. $N$ 은 짝수이다.

선물마다 가격이 있으며, 가격은 $0$ 이상 $3$ 이하의 정수이다. 아기 고양이가 받은 선물 2개에서 얻는 만족도는 두 가격을 XOR한 값이다. 예를 들어 가격이 각각 $1$ , $2$ 인 선물의 만족도는 $1$ XOR $2 = 3$ 이고, 가격이 각각 $3$ , $3$ 인 선물의 만족도는 $3$ XOR $3 = 0$ 이다.

춘배는 만족도 총합이 최대가 되도록 선물을 나눠주려고 한다. 춘배를 위해 이를 계산하는 프로그램을 만들어 주자.

입력

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

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

출력

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

힌트

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

예제2

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