407724: GYM102881 M Baby Ehab's Whining Chance

Baby Ehab had just been stung by increasing subsequences in IOI, so he decided to make himself feel better about his skills. He chose an integer $$$n$$$, wrote down all integers from $$$1$$$ to $$$n$$$, and calculated the longest increasing subsequence like a true genius! Enter Baby Badawy again as envious as ever.

Baby Badawy decided to play a trick on Baby Ehab. He replaced every integer in the sequence with the sum of its digits. Of course, Baby Ehab started crying. It was IOI all over again!

So, his "babysitter" Laggy hired you to find the longest increasing subsequence of this sequence so that Baby Ehab would stop crying.

Hurry up! You only have 300 minutes before Baby Ehab dies of dehydration.

The only line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10 ^ {100000})$$$.

Print the longest increasing subsequence required in the statement.

10

9

99

18

777

24