题目描述

给你一个长度为 $n$ 的数组，你需要将其划分为若干个连续段。对于一种划分，定义其权值为，求出每段的段内所有元素 xor 值，再把所有段的 xor 值相加即为权值。

你需要计算对于所有划分，这个权值的最小、最大值分别是多少。

输入格式

第一行一个整数 $n$。

接下来一行，$n$ 个整数 $a_i$，描述这个数组。

输出格式

一行两个整数，分别为权值的最小、最大值。

样例输入

4
1 4 2 3

样例输出

4 10

数据范围

对于$30\%$的数据，$n\leq 20$

对于另外$40\%$的数据，$n\leq 2000, a_i\leq 2000$

对于所有数据，$1\leq n\leq 10^5,0\leq a_i \leq 10^9$