Largest Fibonacci Number Not Exceeding n

Given an integer n, find the largest Fibonacci number that is less than or equal to n without generating the entire Fibonacci sequence up to n. The Fibonacci sequence is defined as follows:

\(F_0 = 0, \quad F_1 = 1,\)

and for \(n \ge 2\),

\(F_n = F_{n-1} + F_{n-2}.\)

Your task is to compute the maximum Fibonacci number \(F_k\) such that \(F_k \le n\). For example, when \(n = 1000\), the largest Fibonacci number not exceeding 1000 is 987.

The solution must read input from stdin and output the result to stdout.

inputFormat

Input consists of a single line containing a non-negative integer n (\(0 \le n \le 10^9\)).

outputFormat

Output a single integer, which is the largest Fibonacci number less than or equal to n.

1000

987