시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 75 12 9 32.143%

문제

수열 A와 정수 N이 주어진다. N은 2의 제곱꼴이고, A의 각 원소는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다.

0보다 크거나 같고, N-1보다 작거나 같은 정수 B를 골라서, 새로운 수열 C를 만들 수 있다. 각각의 i에 대해서, Ci = Ai xor B로 C를 만든다.

그 다음, C에서 i < j 이면서 Ci < Cj인 (i, j)쌍의 개수를 센다.

B를 적절히 골라서 이러한 쌍의 개수의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 230), 둘째 줄에 수열 A의 크기 M (2 ≤ M ≤ 131072), 셋째 줄에 수열 A의 각 원소 Ai가 주어진다.

출력

i < j 이면서 Ci < Cj인 (i, j)쌍의 개수의 최대값을 출력한다.

예제 입력 1

4
6
3 2 1 0 3 2

예제 출력 1

8

예제 입력 2

8
8
2 5 7 2 3 5 2 5

예제 출력 2

13

예제 입력 3

8
7
3 0 7 2 7 4 3

예제 출력 3

12

예제 입력 4

32
15
7 9 0 4 9 31 2 26 11 21 4 16 13 11 6

예제 출력 4

60

힌트

예제 1의 경우에 B=3을 고르면, C = [0, 1, 2, 3, 0, 1]이 된다. 이 때, i < j이면서 Ci < Cj인 쌍의 개수는 8개이다.

출처