시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 78 34 29 72.500%

문제

진벽이와 미야는 XOR 포커라는 게임을 하고 있다. 서로 정수가 적힌 카드를 N장 받고, 받은 카드 중 일부를 적절히 골라 점수를 계산하여 점수가 더 높은 쪽이 이기는 게임이다.

점수를 계산하는 방법은 다음과 같다.

  1. 주어진 카드 중 짝수 개의 카드를 고른다. (0개는 고를 수 없다)
  2. 고른 카드에 적힌 수들의 XOR 값을 점수로 한다. (여러 정수의 XOR 값의 정의는 예제 밑의 '노트'에 나와 있다.)

예를 들어서, 미야가 현재 {1, 2, 3, 3, 5} 가 적힌 카드를 가지고 있다고 하자. {2, 3, 3, 5} 을 고르면 2 $\oplus$ 3 $\oplus$ 3 $\oplus$ 5 = 7이 점수가 된다. 똑같이 7이 되는 {1, 3, 5} 는 홀수개이기 때문에 고를 수 없다.

미야는 승부욕이 강해서 진벽이를 꼭 이기고 싶다. 미야가 승부에서 이길 수 있도록 도와주자.

입력

첫 번째 줄에는 미야가 가진 카드의 개수 N 이 주어진다. (2 ≤ N ≤ 100,000)

두 번째 줄부터 N개의 줄에 걸쳐 미야의 i 번째 카드에 적힌 수 ai가 주어진다. (0 ≤ ai ≤ 1018)

출력

첫 번째 줄에 미야가 주어진 카드 XOR 포커를 할 때 만들 수 있는 점수의 최대값을 출력한다.

예제 입력 1

5
1
2
3
3
5

예제 출력 1

7

예제 입력 2

4
8
2
4
1

예제 출력 2

15

예제 입력 3

7
765
876
961
315
346
825
283

예제 출력 3

1010

노트

양의 정수들 x1, x2, ..., xN 의 XOR 값은 다음과 같이 정의된다.

XOR 값을 X라고 하자. X를 이진법으로 나타낼 때, x1, x2, ..., xN2k의 자리가 1인 수가 홀수 개 있으면 X2k의 자리는 1이며, 짝수 개 있으면 0이다.