Golomb Sequence

The Golomb Sequence is a self-descriptive sequence denoted by \(G(n)\) with two interesting properties:

• For every positive integer \(n\), the number \(n\) appears exactly \(G(n)\) times in the sequence.
• The sequence is non-decreasing.

For example, the first several values are given in the table below:

Given an integer \(n\), compute \(G(n)\).

inputFormat

The input consists of a single integer \(n\) on one line.

outputFormat

Output the value of \(G(n)\) for the given input \(n\).

sample

1

1