Binary Gap

Given a positive integer \( n \), convert it to its binary representation and determine the length of the longest sequence of consecutive zeros that is surrounded by ones at both ends. This sequence is called the binary gap. For example, if \( n = 9 \) the binary representation is 1001 and the longest binary gap is of length 2. If there is no such gap, output 0.

Note: The binary representation of the number is obtained by converting \( n \) to base 2 (i.e. \( 2 \)).

inputFormat

The input consists of a single line containing one integer \( n \) (where \( 1 \leq n \leq 10^9 \)).

outputFormat

Output a single integer representing the length of the longest binary gap of \( n \). If no such gap exists, output 0.

9

2