Highest Denomination Coin

You are given an integer v and a special coin system. The coin denominations are generated by the following recurrence:

\(a_1 = 1,\; a_2 = 2\), and for \(n \ge 3\), \(a_n = 1 + \sum_{i=1}^{n-1}a_i\).

Given \(v\), your task is to determine the highest coin denomination \(a_k\) such that \(a_k \le v\). For example, if \(v = 5\), the coin denominations generated are \(1, 2, 4, \dots\) and the answer is 4.

Note: The input value \(v\) is guaranteed to be a positive integer.

inputFormat

The input consists of a single line containing an integer \(v\) representing the maximum value.

outputFormat

Output a single integer which is the highest denomination in the coin sequence that does not exceed \(v\).

5

4