#include <bits/stdc++.h>
using namespace std;
const int maxn = 300005;
const int maxm = 1000005;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
int n, a[maxn], cnt[maxn][2], tot, col[maxn], mark[maxn][2];
long long inv = 0;
int solve(int cur) {
  int ct = 0;
  long long ans1 = 0, ans2 = 0;
  for (register int i = (0); i < (tot); ++i) cnt[i][0] = cnt[i][1] = 0;
  for (register int i = (0); i < (n); ++i) {
    if (a[i] & (1 << cur)) {
      cnt[col[i]][1]++;
      ans2 += cnt[col[i]][0];
    } else {
      cnt[col[i]][0]++;
      ans1 += cnt[col[i]][1];
    }
  }
  for (register int i = (0); i < (tot); ++i) {
    mark[i][0] = mark[i][1] = -1;
  }
  tot = 0;
  for (register int i = (0); i < (n); ++i) {
    int o = (a[i] & (1 << cur)) > 0;
    if (mark[col[i]][o] == -1) {
      mark[col[i]][o] = tot++;
      col[i] = mark[col[i]][o];
    } else {
      col[i] = mark[col[i]][o];
    }
  }
  inv += min(ans1, ans2);
  if (ans1 < ans2) {
    return 0;
  } else if (ans1 > ans2) {
    return 1 << cur;
  } else
    return 0;
}
int main() {
  rd(&n);
  rd(a, n);
  tot = 1;
  int ans = 0;
  for (register int i = (30); i >= (0); --i) {
    ans |= solve(i);
  }
  wrn(inv, ans);
}

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given an array a consisting of n non-negative integers. You have to choose a non-negative integer x and form a new array b of size n according to the following rule: for all i from 1 to n, b_i = a_i ⊕ x (⊕ denotes the operation [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)).

An inversion in the b array is a pair of integers i and j such that 1 ≤ i < j ≤ n and b_i > b_j.

You should choose x in such a way that the number of inversions in b is minimized. If there are several options for x — output the smallest one.

Input

First line contains a single integer n (1 ≤ n ≤ 3 ⋅ 10^5) — the number of elements in a.

Second line contains n space-separated integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

Output

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

Examples

Input


4
0 1 3 2


Output


1 0


Input


9
10 7 9 10 7 5 5 3 5


Output


4 14


Input


3
8 10 3


Output


0 8

Note

In the first sample it is optimal to leave the array as it is by choosing x = 0.

In the second sample the selection of x = 14 results in b: [4, 9, 7, 4, 9, 11, 11, 13, 11]. It has 4 inversions:

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



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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300005;
const int maxm = 1000005;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
int n, a[maxn], cnt[maxn][2], tot, col[maxn], mark[maxn][2];
long long inv = 0;
int solve(int cur) {
  int ct = 0;
  long long ans1 = 0, ans2 = 0;
  for (register int i = (0); i < (tot); ++i) cnt[i][0] = cnt[i][1] = 0;
  for (register int i = (0); i < (n); ++i) {
    if (a[i] & (1 << cur)) {
      cnt[col[i]][1]++;
      ans2 += cnt[col[i]][0];
    } else {
      cnt[col[i]][0]++;
      ans1 += cnt[col[i]][1];
    }
  }
  for (register int i = (0); i < (tot); ++i) {
    mark[i][0] = mark[i][1] = -1;
  }
  tot = 0;
  for (register int i = (0); i < (n); ++i) {
    int o = (a[i] & (1 << cur)) > 0;
    if (mark[col[i]][o] == -1) {
      mark[col[i]][o] = tot++;
      col[i] = mark[col[i]][o];
    } else {
      col[i] = mark[col[i]][o];
    }
  }
  inv += min(ans1, ans2);
  if (ans1 < ans2) {
    return 0;
  } else if (ans1 > ans2) {
    return 1 << cur;
  } else
    return 0;
}
int main() {
  rd(&n);
  rd(a, n);
  tot = 1;
  int ans = 0;
  for (register int i = (30); i >= (0); --i) {
    ans |= solve(i);
  }
  wrn(inv, ans);
}

```