You are given an array aa consisting of nn non-negative integers. You have to choose a non-negative integer xx and form a new array bb of size nn according to the following rule: for all ii from 11 to nn, bi=ai⊕xb_i=a_i⊕x (⊕⊕ denotes the operation bitwise XOR).
An inversion in the b array is a pair of integers ii and jj such that 1≤i<j≤n1≤i<j≤n and bi>bjb_i>b_j.
You should choose xx in such a way that the number of inversions in bb is minimized. If there are several options for xx — output the smallest one.

Input

First line contains a single integer nn (1≤n≤3⋅105)(1≤n≤3⋅10^5) — the number of elements in aa.
Second line contains nn space-separated integers a1,a2,⋯ ,ana_1, a_2, \cdots, a_n (0≤ai≤1090≤a_i≤10^9), where aia_i is the ii-th element of aa.

Output

Output two integers: the minimum possible number of inversions in bb, and the minimum possible value of xx, which achieves those number of inversions.

Examples

input

1
2
4  
0 1 3 2

output

1
1 0

input

1
2
9
10 7 9 10 7 5 5 3 5

output

1
4 14

input

1
2
3
8 10 3

output

1
0 8

Note

In the first sample it is optimal to leave the array as it is by choosing x=0x=0.
In the second sample the selection of x=14x=14 results in bb: [4,9,7,4,9,11,11,13,11][4,9,7,4,9,11,11,13,11]. It has 44 inversions:

  • i=2,j=3i=2, j=3;
  • i=2,j=4i=2, j=4;
  • i=3,j=4i=3, j=4;
  • i=8,j=9i=8, j=9.

In the third sample the selection of x=8x=8 results in b:[0,2,11]b: [0,2,11]. It has no inversions.

Translation

给出序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，找出 xx，使得序列所有元素都与 xx 进行异或运算后，得到的逆序对个数最少。当有多个满足条件的 xx 存在时，输出最小的。

Idea

将每个数的二进制形式从高位到低位存在字典树中。我们考虑字典树的其中一棵子树 TSubT_{Sub}，由于两个数的大小取决于它们二进制位上第一个不同的高位；因此，TSubT_{Sub} 的左子树里的所有数字都小于右子树中的数。只要枚举左子树里有多少数字下标比右子树的下标大，就能得到 TSubT_{Sub} 中的逆序对个数。
接下来考虑贪心构造 xx 的过程。我们从低位到高位构造 xx，每次考虑 xx 第 ii 位取 00 或 11 时产生的效果。假设当且考察到 xx 的第 ii 位，若 xx 的第 ii 位取 00，就表明保持所有数字的第 ii 位不变；若 xx 取 11，表面要取反所有数字的第 ii 位，即对换第 ii 层节点的左右儿子。
因此，我们需要开两个数组分别记录数字第 ii 位保持原样和取反产生的逆序对个数。自底向上遍历字典树节点并枚举其左右儿子包含数字的下标即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1416C
Date: 9/29/2020
Description: 01-Trie
*******************************************************************/
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5000006;
int tot;//Trie节点数量
int trie[N][2];
vector<int>ID[N];//节点表示数字的下标
int n;
ll f[N][2];//表示第i位保持不变或反转的逆序对个数
void insert(const int,const int);
void DFS(const int,const int);
int main(){
	cin>>n;
	int i;
	for(i=1;i<=n;i++){
		int temp;
		scanf("%d",&temp);
		insert(temp,i);
	}
	DFS(0,29);
	ll ans=0;
	int x=0;
	for(i=0;i<=29;i++){
		ans+=min(f[i][0],f[i][1]);
		if(f[i][1]<f[i][0]){
			x|=1<<i;//低位向高位构造
		}
	}
	cout<<ans<<' '<<x<<endl;
	return 0;
}
void insert(const int x,const int index){
	int p=0;
	for(register int i=29;i>=0;i--){
		const bool bit=(x>>i)&1;
		if(!trie[p][bit]){
			trie[p][bit]=++tot;
		}
		p=trie[p][bit];
		ID[p].push_back(index);//节点p包含的数字下标
	}
}
void DFS(const int x,const int bit){
	if(trie[x][0]){
		DFS(trie[x][0],bit-1);
	}
	if(trie[x][1]){
		DFS(trie[x][1],bit-1);
	}
	if(!trie[x][0]||!trie[x][1]){
		return;
	}
	ll sum=0;
	for(auto u:ID[trie[x][0]]){
		int p=trie[x][1];
		//ID中有序，直接二分计数
		sum+=lower_bound(ID[p].begin(),ID[p].end(),u)-ID[p].begin();
	}
	f[bit][0]+=sum;
	f[bit][1]+=1ll*ID[trie[x][0]].size()*ID[trie[x][1]].size()-sum;//容斥原理
}