USACO/shuffle

来自"NOCOW"

Cow Shuffle [Piele, 2001]

Each time cows shuffle a deck of 2N (1 <= N <= 9,000) cards marked 1..2N
they do it as follows:

* Cut the deck exactly in half to form two piles (A and B) of N cards each.
  A is the top N cards and B is the bottom N cards.

* Combine the cards back together into a single pile by taking one card
  from pile A and placing it face down on a new pile and then one card from
  pile B and placing it face down on top of the first card, then one from
  A and one from B and so on until all the cards are perfectly shuffled
  back into a single pile.

They repeat this cow shuffle again and again until the cards are back in
their original order.

Given N, how many cow shuffles does it take to return the cards to their
original order?

EXAMPLE:

Let N be 3; therefore, the the cards are {1, 2, 3, 4, 5, 6} and the
shuffles go like this:

orig   shuf1  shuf2   shuf3  shuf4
  1      6      1      6      1
  2      3      5      4      2   
  3   -> 5   -> 4   -> 2   -> 3
  4      2      3      5      4
  5      4      2      3      5
  6      1      6      1      6

So, four cow shuffles suffice to put the deck of 2*3 cards back in order.
 
PROBLEM NAME: shuffle

INPUT FORMAT:

A single line with the integer N

SAMPLE INPUT (file shuffle.in):

3

OUTPUT FORMAT:

A single line with the integer number of shuffles required to return
2N cards to their original order.

SAMPLE OUTPUT (file shuffle.out):

4