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
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
Output the total number of edges crossed in the walk.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 11 10 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 4 1 3 5 7 |
12 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 4 0 1 2 3 |
4 |
| Sample Input 4 | Sample Output 4 |
|---|---|
40 8 1099511627775 1 1 49 97 0 33 322347 |
380 |
