최솟값, 최댓값

시간 제한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은 두 수를 동일한 길이의 이진수로 나타내었을 때 동일한 길이의 이진수를 반환하는 연산이다. 반환값의 $k$ 번째 숫자는 두 이진수 입력의 $k$ 번째 위치의 숫자가 같다면 $0$ , 다르다면 $1$ 이 된다.