Minimum Swaps to Alternate Sequence

You are given a positive integer \(n\). Initially, you have a sequence composed of \(n\) ones followed by \(n\) zeros and then two underscores, which denote empty slots. In other words, the initial sequence is:

[ \underbrace{\tt 1,1,\cdots,1}{n \text{ ones}},\underbrace{\tt 0,0,\cdots,0}{n \text{ zeros}},\verb!__! ]

The goal is to reach the final sequence by applying a series of swap moves. The final sequence should have the first \(2n\) positions arranged in alternating order of \(1\) and \(0\) (i.e. \(1,0,1,0,\ldots,1,0\)) followed by the two underscores. That is, the target sequence is:

[ \underbrace{\tt 1,0,1,0,\cdots,1,0}_{2n \text{ digits (alternating pattern)}},\verb!__! ]

The only move allowed is the following: pick any two consecutive non‐blank characters (i.e. digits) in the sequence and swap them with the two underscores. More precisely, if the two underscores currently occupy some positions, you may choose any two adjacent digits (which are not underscores) and swap their positions with the underscores. After the move, the chosen pair occupies the underscore positions, and their original positions become underscores.

For example, when \(n = 4\) one optimal solution is:

• Initial state: 11110000__
• Step 1: __11000011
• Step 2: 101__00011
• Step 3: 1010100__1
• Step 4: 10101__001
• Step 5: 10101010__

It can be proved that the minimum number of moves needed is 5.

Your task is: given \(n\), compute the minimum number of swap moves required to turn the initial sequence into the target alternating sequence.

inputFormat

The input consists of a single integer \(n\) where \(n \ge 1\).

outputFormat

Output a single integer representing the minimum number of swap moves required.

Note: For \(n=1\) the initial sequence is already in the target form, so the answer is 0.

sample

1

0