30961번 - 최솟값, 최댓값

문제

수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $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ドル$이 된다.