Minimum Toggling Operations

You are given a multiple-answer question with n options. The correct answer is a nonempty subset of these options. Initially, no option is selected. You may perform the following operation any number of times:

• Select (check) an option that is currently not selected.
• Deselect (uncheck) an option that is currently selected.

You immediately pass the question when the set of selected options exactly matches the correct answer. Since the problem and the options are obscured, you plan to try every possible answer. In the worst-case scenario, what is the minimum number of operations required to guarantee passing the question?

Note: The answer always contains at least one option.

It can be shown that an optimal strategy corresponds to traversing all nonempty subsets of the options in a Gray code order. Consequently, if the total number of nonempty subsets is \(2^n - 1\), then the minimum number of operations required in the worst case is also \(2^n - 1\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 30), which represents the number of options.

outputFormat

Output a single integer representing the minimum number of operations required in the worst-case scenario, which is \(2^n - 1\) in latex format.

sample

1

1