최솟값, 최댓값

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

요약

수열 A의 모든 비어 있지 않은 부분수열에서 최솟값과 최댓값의 곱을 구한 뒤, 그 값들의 XOR을 출력합니다.

문제

수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$ 인 수열 $A$ 가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라.

첫 번째 줄에 $N$ 이 주어진다. $(1 \le N \le 10^6)$

두 번째 줄에 수열 $A$ 를 이루는 정수 $N$ 개가 순서대로 주어진다. $(0 \le A_i \le 10^9)$

첫 번째 줄에 문제의 답을 출력한다.

부분수열은 수열에서 순서를 유지하면서 원소를 $1$ 개 이상 $N$ 개 이하로 고른 수열이다. 연속일 필요는 없다.

XOR은 두 수를 같은 길이의 이진수로 나타냈을 때, 같은 자리의 숫자가 같으면 $0$ , 다르면 $1$ 을 반환하는 연산이다. 결과의 $k$ 번째 자리 숫자는 두 입력의 $k$ 번째 자리 숫자가 같으면 $0$ , 다르면 $1$ 이다.