class Solution {

public:

    vector<int> lexicalOrder(int n) {

        vector<int> ans;

        int cur = 1;

        for (int i = 1; i <= n; ++i) {

            ans.push_back(cur);

            if (cur * 10 <= n) {

                cur *= 10;

            } else if (cur % 10 != 9 && cur + 1 <= n) {

                cur++;

            } else {

                cur += 10;

                cur -= cur % 10;

                while (cur % 10 == 0) cur /= 10;

            }

        }

        return ans;

    }

};