and xor or
题号：NC274767
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的序列 a，jackle 想让你求出有多少个区间 [l,r] 满足如下条件：
  • 1\leq l\leq r\leq n
  • 2^{k_1}\leq (a_l\ \&\ a_{l+1}\ \&...\&\ a_r)\oplus(a_l\ |\ a_{l+1}\ |...|\ a_r)< 2^{k_2}
其中 \&，|，\oplus，分别表示按位与，按位或，按位异或。

输入描述:

第一行输入 3 个整数 n\ (1\leq n\leq 5\times 10^5)，k_1, k_2\ (0\leq k_1<k_2\leq 10^9)。
第二行输入 n 个整数 a_i\ (0\leq a_i\leq 10^{18})。

输出描述:

输出满足条件的区间数量。
示例1

输入

复制 
4 0 2
2 1 4 3

输出

复制 
1

说明

只有区间 [1,2] 满足条件：2^0\leq (2\ \& \ 1)\oplus(2\ |\ 1)=3<2^2
示例2

输入

复制 
6 0 4
7 6 7 6 7 7

输出

复制 
14