XOR INVERSE

Xem PDF

Điểm: 550 Thời gian: 2.0s Bộ nhớ: 254M Input: bàn phím Output: màn hình
  • Cho một mảng \(a\) gồm \(n\) số nguyên không âm.

  • Nhiệm vụ của bạn là: Chọn số nguyên không âm \(x\) để xây dựng mảng \(b\) thỏa mãn các điều kiện sau:

  • \(b_i=a_i\oplus x\) (\(\oplus\) ở đây chính là phép toán XOR)

  • Số cặp nghịch thế trong mảng \(b\) nhỏ nhất có thể. (Chú ý: Cặp nghịch thế của mảng \(b\) là cặp số \(i,j\) thỏa mãn \(1\le i<j\le n\)\(b_i>b_j\))

Nếu có nhiều đáp án \(x\) thỏa mãn thì chọn số \(x\) không âm nhỏ nhất. Sau đó in ra màn hình số lượng cặp nghịch thế có trong mảng \(b\) tương ứng với số \(x\) đó và số \(x\) không âm nhỏ nhất đó.

Input

  • Dòng thứ nhất chứa số nguyên \(n(1\le n\le 3.10^5)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(0\le a_i\le 10^9)\).

Output

  • In ra đáp án cần tìm.

Example

Test 1

Input
4
0 1 3 2
Output
1 0

Bình luận