Problem D
Long Walk

To ignore his impending doom, Jimmy-Jimmy likes to imagine going for long walks. Today, he is imagining a walk on a graph $G$. $G$ has $2^ n$ nodes, labelled $0,1,2,\dots ,2^ n-1$. For each $i\in \{ 1,2,\dots ,2^ n-1\} $, $G$ has a bidirectional edge between node $i$ and node $2i\pmod{2^ n}$.

Jimmy-Jimmy wants to visit $m$ nodes of $G$ in a specific order. He starts his walk at node $a_1$. From there, he takes the shortest path along the edges of $G$ to $a_2$, then takes the shortest path from $a_2$ to $a_3$, and so on, until he reaches node $a_ m$, where his walk concludes. Can you determine the total number of edges that Jimmy-Jimmy will imagine walking across?


Input begins with two space-separated integers $1\le n\le 62$ and $2\le m\le 10^6$. The next line contains $m$ space-separated integers $a_1,a_2,\dots ,a_ m$, where $0\le a_ i\le 2^ n-1$ for all $i$.


Output the total number of edges crossed in the walk.

Sample Input 1 Sample Output 1
4 2
11 10
Sample Input 2 Sample Output 2
3 4
1 3 5 7
Sample Input 3 Sample Output 3
2 4
0 1 2 3
Sample Input 4 Sample Output 4
40 8
1099511627775 1 1 49 97 0 33 322347

Please log in to submit a solution to this problem

Log in