Minimum Moves for Chinese Rings Puzzle

This problem is a variation of the classic Chinese Rings (or "Nine Linked Rings") puzzle. The puzzle involves n rings placed on a sword. Each ring can be either attached (represented by 1) or detached (represented by 0). The following two rules determine which ring can be manipulated:

• Rule 1: The first ring (i.e. the rightmost ring) can be attached or detached at any time.
• Rule 2: For any k ≥ 1, if the k^th ring is still attached and all rings to the right of it are detached, then the (k+1)^th ring (its immediate left neighbor) can be attached or detached at will.

For example, consider the case of 4 rings. We denote an attached ring by 1 and a detached ring by 0. The initial state is 1111 (all rings attached), and one sequence of optimal moves is:

1. 1101 (detach the 2^nd ring by Rule 2)
2. 1100 (detach the 1^st ring by Rule 1)
3. 0100 (detach the 4^th ring by Rule 2)
4. 0101 (attach the 1^st ring by Rule 1)
5. 0111 (attach the 2^nd ring by Rule 2)
6. 0110 (detach the 1^st ring by Rule 1)
7. 0010 (detach the 3^rd ring by Rule 2)
8. 0011 (attach the 1^st ring by Rule 1)
9. 0001 (detach the 2^nd ring by Rule 2)
10. 0000 (detach the 1^st ring by Rule 1)

Thus, detaching all 4 rings requires at least 10 moves. Similarly, detaching 9 rings requires at least 341 moves.

It turns out that the answer can be expressed by a simple formula. Let \( f(n) \) be the minimum number of moves needed to detach all n rings. Then:

[ f(n)=\begin{cases} \frac{2^{n+1}-1}{3}, & \text{if } n \text{ is odd},\[8pt] \frac{2^{n+1}-2}{3}, & \text{if } n \text{ is even}. \end{cases} ]

Given n, calculate \( f(n) \).

inputFormat

The input consists of a single integer n indicating the number of rings. You can assume that n ≥ 1.

outputFormat

Output the minimum number of moves required to detach all n rings.

sample

1

1