<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

375. Amplifiers
Time limit per test: 1.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Scientist Shurik needs voltage that is N times more that the standard voltage in the wall outlet for power supply for his time machine. The standard voltage is equal to one Bervolt. Shurik decided to use voltage amplifiers. In the nearby shop he found the amplifiers of two types, the first type creates voltage 2X-1 Bervolt from X Bervolt, the second one creates voltage 2X+1 Bervolt from X Bervolt. The number of amplifiers in the shop is unlimited. Shurik wants to build a sequence of amplifiers from the outlet to the time machine. Of course he wants to minimize the number of amplifiers. Help him.

Input
A single integer 1 ≤ N≤ 2· 109.

Output
If it is possible to make such scheme, output in the first line the minimal possible number of amplifiers. The second line in this case is to contain the sequence of amplifiers from the outlet to the time machine. Use number 1 for the first-type amplifiers and number 2 for second-type amplifiers.

If there is no solution, output "No solution" (without quotes).

Example(s)
sample input
sample output
5
2
2 1

<|response|>
1. Abridged problem statement  
   Starting from voltage 1, you have unlimited amplifiers of two types:  
   • Type 1: X → 2·X − 1  
   • Type 2: X → 2·X + 1  
   Given a target N (1 ≤ N ≤ 2·10⁹), find the shortest sequence of amplifier types to reach exactly N volts, or report “No solution” if impossible.

2. Key observations  
   • Every operation starting from 1 produces an odd voltage. Hence if N is even, there is no solution.  
   • Instead of building forward from 1 to N (which branches exponentially), work backwards from N to 1.  
     – The inverse of Type 1 (X→2X−1) is N→(N+1)/2.  
     – The inverse of Type 2 (X→2X+1) is N→(N−1)/2.  
   • Since N is odd, both (N±1)/2 are integers, but exactly one of them is odd. To ensure the next reverse step remains valid (odd), always pick the odd predecessor.  
   • Each reverse step roughly halves N, so the process takes O(log N) steps. Reversing the recorded steps yields the forward sequence.

3. Full solution approach  
   1. Read N.  
   2. If N is even, print “No solution” and stop.  
   3. Initialize an empty list `ops` to record amplifier types in reverse.  
   4. While N > 1:  
      a. Compute a = (N−1)/2  (would be the predecessor if the last forward step was Type 2)  
      b. Compute b = (N+1)/2  (predecessor if last forward step was Type 1)  
      c. Exactly one of a, b is odd.  
         – If a is odd, append 2 to `ops` and set N = a.  
         – Otherwise append 1 to `ops` and set N = b.  
   5. Reverse `ops` to obtain the forward sequence of amplifier types.  
   6. Print the length of `ops` and then the sequence (space-separated).  
   7. Special case: if N=1 initially, the loop is skipped, `ops` is empty; print 0 and an empty second line.

4. C++ implementation with detailed comments  
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    cin >> N;
    // If target is even, it's unreachable (all generated voltages are odd).
    if (N % 2 == 0) {
        cout << "No solution\n";
        return 0;
    }

    // Record amplifier types in reverse order
    vector<int> ops;
    // Work backwards until we reach 1
    while (N > 1) {
        long long a = (N - 1) / 2; // inverse of Type 2
        long long b = (N + 1) / 2; // inverse of Type 1
        // Exactly one of a, b is odd: choose that to keep the chain valid
        if (a % 2 == 1) {
            ops.push_back(2); // means forward step was Type 2: X->2X+1
            N = a;
        } else {
            ops.push_back(1); // forward step was Type 1: X->2X-1
            N = b;
        }
    }

    // Reverse to get the forward path from 1 to original N
    reverse(ops.begin(), ops.end());

    // Output result
    cout << ops.size() << "\n";
    for (int t : ops) {
        cout << t << " ";
    }
    cout << "\n";
    return 0;
}

5. Python implementation with detailed comments  
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    # Even targets are impossible
    if n % 2 == 0:
        print("No solution")
        return

    ops = []
    # Work backwards until n becomes 1
    while n > 1:
        a = (n - 1) // 2  # predecessor if last step was Type 2
        b = (n + 1) // 2  # predecessor if last step was Type 1
        # Pick the odd one to keep the chain valid
        if a % 2 == 1:
            ops.append(2)  # forward step was Type 2
            n = a
        else:
            ops.append(1)  # forward step was Type 1
            n = b

    # Reverse to obtain the forward sequence
    ops.reverse()

    # Print result
    print(len(ops))
    if ops:
        print(" ".join(map(str, ops)))

if __name__ == "__main__":
    main()