题目描述

给定一个长度为 $n$ 的数组 $a$，你可以选择一个范围在 $1$ 到 $n$ 之间的正整数 $k$，并选择数组 $a$ 的 $k$ 个非空子区间，使得数组 $a$ 的每个元素都处在且仅处在一个区间中。换句话说，便是将数组 $a$ 划分为 $k$ 个区间。定义一个区间的权值为区间中所有元素按位或运算的结果。

求两项内容：

• 所有 $k$ 个区间的权值之和的最小值；
• 在保证所有 $k$ 个区间的权值之和达到上述最小值的前提下，可以选择的 $k$ 的最大值。

输入格式

第一行包含一个整数 $n$，表示数组 $a$ 的长度。

第二行包含 $n$ 个整数，表示数组 $a$（用空格分隔）。

输出格式

输出两个整数，用空格分隔： 第一个数表示所有 $k$ 个区间的权值之和的最小值； 第二个数表示在取得该最小值的前提下可以选择的 $k$ 的最大值。

样例输入

4
1 0 10 2

样例输出

11 3

说明

样例解释

可以选择 $k=3$，分成三个区间分别为 $[1,1]$、$[2,2]$、$[3,4]$。三个位区间权值分别为 $1,0,10$，和为 $11$。可以证明不存在使所有 $k$ 个区间权值之和更小的划分；在所有使权值之和为 $11$ 的划分中，$k$ 的最大可取值为 $3$。

数据范围

• 对于 $20\%$ 的评测数据，$1\le n\le 500$。
• 对于 $40\%$ 的评测数据，$1\le n\le 5\times 10^{3}$。
• 对于 $100\%$ 的评测数据，$1\le n\le 2\times 10^{5}$，且 $0\le a_i\le 2^{30}-1$。