Count Legal Sequences

Given a positive integer \(n\), you are to count the number of legal sequences that can be constructed according to the following rules:

1. A sequence consisting of only the number \(n\) is legal.
2. If a sequence \(a_1, a_2, \ldots, a_k\) is legal, then appending a positive integer \(x\) at the end to form \(a_1, a_2, \ldots, a_k, x\) is legal if and only if \(x \leq \frac{a_k}{2}\).

Two legal sequences \(a\) and \(b\) are considered different if and only if they have different lengths or there exists an index \(i\) (\(1 \leq i \leq |a|\)) such that \(a_i \neq b_i\).

Find the total number of legal sequences that can be constructed starting from \(n\). The answer is defined by the recurrence:

[ f(n)=1+\sum_{x=1}^{\lfloor n/2 \rfloor} f(x), \quad f(1)=1. ]

Output the number \(f(n)\).

inputFormat

The input consists of a single positive integer \(n\) (\(1 \leq n \leq 10^6\), or as specified by the problem constraints).

Input Format:

 n

outputFormat

Output a single integer, which is the total number of legal sequences that can be constructed following the rules.

Output Format:

 answer

sample

6

6