C++, O(10*n)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string getString(int num){\n        string ret = "";\n        while(num>0){\n            ret+=\'0\'+(num%10);\n            num/=10;\n        }\n        reverse(ret.begin(),ret.end());\n        return ret;\n    }\n    long long getNum(string s){\n        long long ret = 0;\n        for(int i = 0;i<s.size();i++){\n            ret*=10;\n            ret+=(s[i]-\'0\');\n        }\n        return ret;\n    }\n    long long getBiggerPal(int num){\n        if(num<10) return num;\n        string cur = getString(num);\n        int sz = cur.size();\n        if(sz%2 == 0){\n            for(int i = sz/2;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2+1)];\n            }\n            long long retNum = getNum(cur);\n            if(retNum >= num) return retNum;\n            cur = cur.substr(0,sz/2);\n            long long newNum = getNum(cur);\n            newNum++;\n            cur = getString(newNum);\n            cur = cur+cur;\n            for(int i = sz/2;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2+1)];\n            }\n            return getNum(cur);\n        }\n        else{\n            for(int i = sz/2+1;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2)];\n            }\n            long long retNum = getNum(cur);\n            if(retNum >= num) return retNum;\n            cur = cur.substr(0,sz/2 + 1);\n            long long newNum = getNum(cur);\n            newNum++;\n            cur = getString(newNum);\n            cur = cur+cur;\n            cur.pop_back();\n            for(int i = sz/2+1;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2)];\n            }\n            return getNum(cur);\n        }\n    }\n    bool isPow10(int num){\n        while(num>1){\n            if(num%10 > 0) return 0;\n            num/=10;\n        }\n        return num == 1;\n    }\n    long long getLessPal(int num){\n        if(isPow10(num)) return num-1;\n        if(num < 10) return num;\n        if(num == 10) return 9;\n        if(num == 11) return num;\n        string cur = getString(num);\n        int sz = cur.size();\n        if(sz%2 == 0){\n            for(int i = sz/2;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2+1)];\n            }\n            long long retNum = getNum(cur);\n            if(retNum < num) return retNum;\n            cur = cur.substr(0,sz/2);\n            long long newNum = getNum(cur);\n            newNum--;\n            cur = getString(newNum);\n            cur = cur+cur;\n            for(int i = sz/2;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2+1)];\n            }\n            return getNum(cur);\n        }\n        else{\n            for(int i = sz/2+1;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2)];\n            }\n            long long retNum = getNum(cur);\n            if(retNum < num) return retNum;\n            cur = cur.substr(0,sz/2 + 1);\n            long long newNum = getNum(cur);\n            newNum--;\n            cur = getString(newNum);\n            cur = cur+cur;\n            cur.pop_back();\n            for(int i = sz/2+1;i<sz;i++){\n                cur[i] = cur[sz/2-(i-sz/2)];\n            }\n            return getNum(cur);\n        }\n    }\n    long long minimumCost(vector<int>& a) {\n        long long ans = 1e18;\n        sort(a.begin(),a.end());\n        long long sum = 0;\n        int n = a.size();\n        for(int i = 0;i<n;i++){\n            sum+=a[i];\n        }\n        long long pref = 0;\n        for(int i = 0;i<n;i++){\n            pref+=a[i];\n            long long ritSum = sum - pref;\n            long long numBig = getBiggerPal(a[i]);\n            long long leftNeed = (i+1)*(numBig) - pref;\n            long long ritNeed = ritSum - (n-i-1)*numBig;\n           // cout<<a[i]<<" "<<numBig<<" "<<leftNeed+ritNeed<<endl;\n            if(i<n-1 && numBig <= a[i+1]) ans = min(ans,leftNeed + ritNeed);\n            else if(i == n-1) ans = min(ans,leftNeed);\n            long long numLess = getLessPal(a[i]);\n            if(i == 0 || (i>0 && numLess > a[i-1])){\n                pref-=a[i];\n                leftNeed = i*numLess - pref;\n                ritSum+=a[i];\n                ritNeed = ritSum - (n-i)*numLess;\n                ans = min(ans,leftNeed + ritNeed);\n                pref+=a[i];\n            }\n\n        }\n        cout<<getLessPal(1000)<<endl;\n        return ans;\n    }\n};\n```
['C++']