Minimal Operations to Unfasten the Bit Chain

Consider a chain of rings numbered from (1) to (n) on the Bit Chain. Initially, every ring is in a connected state. We want to remove (detach) all rings from the chain, i.e. change every ring’s state from connected to detached. However, you cannot operate on any ring arbitrarily – you may toggle (i.e. change the state of) a ring only under the following rules:

1. The first ring (ring 1) can be toggled (attached or detached) at any time.

2. For any subsequent ring (i) (with (2 \le i \le n)), you are allowed to toggle it only if the previous ring (i-1) is in the connected state and all rings before it (rings (1,2,\dots,i-2)) are detached. In other words, for (i \ge 2) the operation on ring (i) is allowed if and only if [ \text{for } i=2:\quad \text{ring } 1 \text{ is connected}, ]

and for (i \ge 3): [ \text{if } \text{rings } 1,2,\dots,i-2 \text{ are detached and ring } i-1 \text{ is connected}, \text{ then ring } i \text{ can be toggled.} ]

An operation means toggling the state of one ring (changing a connected ring to detached or vice versa). The goal is to have every ring detached (state = detached) in the minimum number of operations. Note that sometimes in order to be allowed to operate on a later ring you must re‐connect one that has already been detached.

For example, if (n=3) then an optimal sequence is as follows (here A denotes connected and D denotes detached):

Initial state: [A, A, A]

1. Toggle ring 1: detach ring 1 (\to [D, A, A]).
2. Toggle ring 2: (not allowed now because ring 1 is detached) so instead, we must postpone operating on ring 2. A better approach is to start with a move on ring 2 while ring1 is still connected.

An optimal solution for (n=3) is:

• Operation 1: Toggle ring 2 (\to [A, D, A]) \t\t(\text{allowed since ring 1 is connected}).
• Operation 2: Toggle ring 1 (\to [D, D, A]).
• Operation 3: Toggle ring 2 (reconnect it) (\to [D, A, A]) \t\t(\text{allowed since ring 1 is detached and ring 2 can be reconnected if the condition holds}).
• Operation 4: Toggle ring 3 (\to [D, A, D]) \t\t(\text{allowed because now for ring 3, rings 1 is detached and ring 2 is connected}).
• Operation 5: Toggle ring 1 (\to [A, A, D]), then finally
• Operation 6: Toggle ring 2 (\to [A, D, D]), and
• Operation 7: Toggle ring 1 (\to [D, D, D]).

It turns out that by a careful re‐ordering the minimum number of operations for (n=3) is 5 (one can show that a shorter sequence is impossible).

Your task is to write a program that, given an integer (n) describing the number of rings on the chain, computes the minimal number of operations needed to detach all rings.

Note: You may assume (1 \le n \le 10). Since the allowed operations depend on the current state of all the rings, one good way to solve the problem is to use a breadth‐first search (BFS) over states represented by a bitmask (with 1 meaning connected and 0 meaning detached).

inputFormat

A single integer (n) denoting the number of rings on the chain.

outputFormat

Output a single integer — the minimal number of operations needed to detach all rings.

sample

1

1