Description

Given a positive integer $n$, construct sequences in the following way.

1. A sequence consisting of only the number $n$ is a valid sequence.
2. By appending a positive integer to the end of a valid sequence, if this integer does not exceed half of the last term of the sequence, the new sequence is also valid.

Please find how many valid sequences there are in total. Two valid sequences $a, b$ are different if and only if their lengths are different, or there exists a positive integer $i \leq |a|$ such that $a_i \neq b_i$.

Input Format

The input consists of a single line with one integer $n$.

Output Format

Output a single integer, the number of valid sequences.

6

6

Hint

Explanation for Sample 1

The sequences that meet the conditions are:

• $6$.
• $6, 1$.
• $6, 2$.
• $6, 3$.
• $6, 2, 1$.
• $6, 3, 1$.

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 10^3$.

Notes

The testdata of this problem comes from the first problem of NOIP 2001 Junior. However, the original statement and the testdata do not match, so the statement has been modified here to match the testdata. The original statement is provided below for reference:

We want to find the number of numbers with the following properties (including the input positive integer $n$).

First input a positive integer $n$ ($n \le 1000$), and then process this integer as follows:

1. Do nothing.
2. Concatenate a positive integer to its left, but this positive integer cannot exceed the original number, or half of the last concatenated number.
3. After adding a number, continue processing according to this rule until no more positive integers can be added.

Thanks to

edback on this problem. The issue with the original statement can be found in this post.

Translated by ChatGPT 5