<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> having length <code>n</code>.</p>

<p>You are allowed to perform a special move <strong>any</strong> number of times (<strong>including zero</strong>) on <code>nums</code>. In one <strong>special</strong> <strong>move</strong> you perform the following steps <strong>in order</strong>:</p>

<ul>
	<li>Choose an index <code>i</code> in the range <code>[0, n - 1]</code>, and a <strong>positive</strong> integer <code>x</code>.</li>
	<li>Add <code>|nums[i] - x|</code> to the total cost.</li>
	<li>Change the value of <code>nums[i]</code> to <code>x</code>.</li>
</ul>

<p>A <strong>palindromic number</strong> is a positive integer that remains the same when its digits are reversed. For example, <code>121</code>, <code>2552</code> and <code>65756</code> are palindromic numbers whereas <code>24</code>, <code>46</code>, <code>235</code> are not palindromic numbers.</p>

<p>An array is considered <strong>equalindromic</strong> if all the elements in the array are equal to an integer <code>y</code>, where <code>y</code> is a <strong>palindromic number</strong> less than <code>10<sup>9</sup></code>.</p>

<p>Return <em>an integer denoting the <strong>minimum</strong> possible total cost to make </em><code>nums</code><em> <strong>equalindromic</strong> by performing any number of special moves.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> 6
<strong>Explanation:</strong> We can make the array equalindromic by changing all elements to 3 which is a palindromic number. The cost of changing the array to [3,3,3,3,3] using 4 special moves is given by |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6.
It can be shown that changing all elements to any palindromic number other than 3 cannot be achieved at a lower cost.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,12,13,14,15]
<strong>Output:</strong> 11
<strong>Explanation:</strong> We can make the array equalindromic by changing all elements to 11 which is a palindromic number. The cost of changing the array to [11,11,11,11,11] using 5 special moves is given by |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11.
It can be shown that changing all elements to any palindromic number other than 11 cannot be achieved at a lower cost.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [22,33,22,33,22]
<strong>Output:</strong> 22
<strong>Explanation:</strong> We can make the array equalindromic by changing all elements to 22 which is a palindromic number. The cost of changing the array to [22,22,22,22,22] using 2 special moves is given by |33 - 22| + |33 - 22| = 22.
It can be shown that changing all elements to any palindromic number other than 22 cannot be achieved at a lower cost.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        N = len(nums)
        nums.sort()

        if N % 2:
            mid = nums[N // 2]

        else:
            mid = (nums[(N // 2) - 1] + nums[N // 2]) // 2

        def create(s):
            return int(s + s[:-1][::-1]), int(s + s[::-1])

        def find(x):    
            if x < 10:
                return x if x > 0 else 1

            if str(x) == str(x)[::-1]:
                return x

            s = str(x)
            n = len(s)
            info = set()
            
            prefix = s[:(n + 1) // 2]
            
            info.update(create(prefix))
            
            prefix_int = int(prefix)
            info.update(create(str(prefix_int - 1)))
            info.update(create(str(prefix_int + 1)))

            info.add(10**n + 1)
            info.add(10**(n - 1) - 1)
            
            info.discard(x)
            
            ans = min(info, key=lambda p: (abs(p - x), p))
            return ans

        def create_2(s, flag):
            if flag:
                return int(s + s[::-1])
            else:
                return int(s + s[-2::-1])

        def prev(n):
            if n == 1:
                return 0
            s = str(n)
            length = len(s)
            flag = (length % 2 == 0)
            
            left_half = s[:(length + 1) // 2]
            palindrome = create_2(left_half, flag)
            
            if palindrome < n:
                return palindrome
            
            new_left_half = str(int(left_half) - 1)
            
            if new_left_half == "0":
                return int("9" * (length - 1))
            
            return create_2(new_left_half, flag)

        def next(n):
            s = str(n)
            length = len(s)
            flag = (length % 2 == 0)
            
            left_half = s[:(length + 1) // 2]
            palindrome = create_2(left_half, flag)
            
            if palindrome > n:
                return palindrome
            
            new_left_half = str(int(left_half) + 1)
            
            if len(new_left_half) > len(left_half):
                return int("1" + "0" * (length - 1) + "1")
            
            return create_2(new_left_half, flag)

        def do(target):
            cost = 0

            for num in nums:
                cost += abs(num - target)

            return cost

        b = find(mid)
        a, c = prev(b), next(b)
        print(a, b, c)

        return min([do(a), do(b), do(c)])
318