Magic with Cards

Interview

Time limit2sMemory limit1024 MB

Summary

Given a deck of 2n cards, find the fewest riffle and scuffle shuffles that move the card at position i to position j, or report -1.

Level: Medium5 of 10
Topics: BFS, Graph, Implementation
Solved: No attempts yet

Problem

Mahsa has been practicing card shuffling for a few months. Tonight she invites her friends over to show off her new skills. She takes a deck of 2n cards and shows the faces of the cards to her friends without changing the deck order. Then someone picks two positions i and j in the deck. Mahsa says she will move the card at position i to position j using only two types of shuffles.

Let the cards in the deck be ⟨c1, c2, ..., c2n⟩. Mahsa may apply the two shuffles as many times as she wants.

Riffle: Split the cards into two parts, ⟨c1, ..., cn⟩ and ⟨cn+1, ..., c2n⟩, and produce ⟨c1, cn+1, c2, cn+2, ..., cn, c2n⟩.

Scuffle: From ⟨c1, c2, ..., c2n⟩, produce ⟨c2, c1, c4, c3, ..., c2n, c2n-1⟩.

Find the minimum number of shuffles Mahsa needs to move the i-th card to the j-th position. Mahsa will work out the rest.

Input

One line with three space-separated integers n, i and j, where 1 ⩽ n ⩽ 10^5 and 1 ⩽ i, j ⩽ 2n.

Output

Print one integer, the minimum number of shuffles needed to move the i-th card to the j-th position. If it is impossible, print -1.

Examples3

Example 1
Input
```
4 3 8
```
Expected output
```
3
```
Example 2
Input
```
5 4 1
```
Expected output
```
5
```
Example 3
Input
```
1 1 1
```
Expected output
```
0
```