Given number ~N~, let's find the first digit from the left that violates the alternating parity, in other words, that is of the same parity as the previous digit. We have two options:

• A. Change the current digit and leave all the previous digits unchanged.
• B. Change a digit previous to this one.

Option A consists of two suboptions: increasing and decreasing the digit. If the digit is ~0~, it can only be increased; if it's ~9~, it can only be decreased; otherwise it can be both increased or decreased. It is evident that it's not worth increasing or decreasing the digit by more than one.

After increasing or decreasing the digit, what to do with the following digits? If we have increased the digit, the resulting number is surely larger than ~N~ so, in order to get closer to it, the following digits should be as small as possible: ~0101 \dots~ or ~1010 \dots~, depending on the parity of the increased digit. Analogously, if we have decreased the digit, the resulting number is surely smaller than ~N~ so, in order to get closer to it, the following digits should be as large as possible: ~9898 \dots~ or ~8989 \dots~, depending on the parity of the decreased digit.

Of course, if we had the option of both increasing and decreasing the digit, it is necessary to find a number closer to ~N~ between the two resulting numbers. We can do this by subtracting and comparing the differences (Python has built-in support for arbitrarily large numbers).

The constraints in the task allowed us to also consider option B. We can attempt to increase and decrease each digit (so that, of course, it remains of different parity than the previous digit), construct the rest of the number using the above mentioned principle and compare the obtained difference with the minimal so far, storing the best solution. However, this wasn't necessary because option B is actually never better than A. The proof is left as an exercise to the reader.