#XMOJ12794. 幸运排序

幸运排序

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:sort.in 输出文件:sort.out

给定长度为 $N$ 的数列 $A$,所有元素互不相同。

你必须恰好执行一次下面的操作:

1. 选出一个整数 $x$,满足 $L \le x \le R$

2. 将数列所有元素替换成 $A_i \ \mathrm{XOR}\ x$

求:有多少个 $x$,可以使得操作之后的数列严格单调递增。

严格单调递增的定义:对所有 $1\le i<N$,满足 $A_i < A_{i+1}$。

输入格式

第一行三个整数 $N,L,R$。

第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

输出格式

输出满足条件的 $x$ 的数量。

样例

样例 1

6 1325 1350
1332 1335 1334 1329 1328 1331

4

样例说明:

例如取 x=1333x=1333,操作后得到 1,2,3,4,5,6{1,2,3,4,5,6},严格递增;取 x=1334x=1334 得到 2,1,0,7,6,5{2,1,0,7,6,5},不满足。

样例 2

4 100 500
1 7 41 23

0

样例说明:

不存在合法的 xx。

样例 3

1 0 10000
1

10001

样例说明:

N=1N=1 时,任意 xx 都合法,一共 1000110001 个。

数据范围

对于 40% 的数据,$N \le 50$。

对于 100% 的数据,$1 \le N \le 2\times 10^5$,$0 \le L \le R < 2^{61}$,$0 \le A_i < 2^{61}$,$i\neq j$ 时 $A_i \neq A_j$。