It's the finals week of Busy Beaver's senior year, and he just remembered about the list of must-do activities to complete before graduating he received during freshman orientation.
You are given an array of $$$N$$$ numbers $$$a_1, \ldots, a_N$$$, where $$$a_i$$$ represents the joy of completing the $$$i^\text{th}$$$ activity.
Due to his limited time at MIT, he has decided to only complete a contiguous subsegment of these activities. Additionally, to make the most out of it, the subsegment must contain at least two activities.
While procrastinating when preparing for his finals, he came up with a sophisticated way of scoring a subsegment. The score of the subsegment from index $$$l$$$ to $$$r$$$ is the minimum XOR of two distinct activities. Formally, the subsegment from index $$$l$$$ to $$$r$$$ has a score of $$$\min\limits_{l \leq i \lt j \leq r} a_i \oplus a_j$$$.
Busy Beaver's favorite number is $$$K$$$, so he would like to calculate the number of subsegments with score $$$K$$$. Can you help him?
The first line contains two integers $$$N$$$, $$$K$$$ ($$$2 \le N \le 10^5$$$, $$$0 \le K \lt 2^{30}$$$).
The second line contains $$$N$$$ space-separated integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \lt 2^{30}$$$).
Output a single integer: the number of contiguous subsegments of size at least two with score $$$K$$$.
- ($$$15$$$ points) $$$N \leq 5000$$$.
- ($$$10$$$ points) $$$K = 0$$$.
- ($$$25$$$ points) Array $$$a$$$ is sorted in non-decreasing order ($$$a_{1} \leq \ldots \leq a_{N}$$$).
- ($$$50$$$ points) No additional constraints.
5 21 3 1 4 5
3
There are three subsegments that should be counted:
- $$$l = 1, r = 2$$$.
- $$$l = 2, r = 3$$$.
- $$$l = 2, r = 4$$$.
