<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()

      # avg = sum(nums)/n
      a = nums[n//2]
      f = False
      if n%2 == 0:
        f = True
      b = nums[n//2-1]
      def getPalindrome(s):
        # print(s)
        if s == s[::-1]:
          return [int(s)]
        n = len(s)
        # print(n,n%2)
        N = int(s)
        if n%2 == 0:
          # print("e")
          t = n//2
          a = s[:t]
          b = int(a)
          c = b-1
          d = b+1
          e = str(b)
          f = str(c)
          g = str(d)
          e = e+e[:t][::-1]
          f = f+f[:t][::-1]
          g = g+g[:t][::-1]
          b = int(e)
          c = int(f)
          d = int(g)

          d1 = abs(N-b)
          d2 = abs(N-c)
          d3 = abs(N-d)
          D = min(d1,d2,d3)
          res = []
          # if d1 == D:
          res.append(b)
          # if d2 == D:
          res.append(c)
          # if d3 == D:
          res.append(d)
          # print(res)
          return res

        else:
          # print("o")
          t = n//2
          a = s[:t+1]
          b = int(a)
          c = b-1
          d = b+1
          # print(b,c,d)
          e = str(b)
          f = str(c)
          g = str(d)
          e = e+e[:t][::-1]
          f = f+f[:t][::-1]
          g = g+g[:t][::-1]
          b = int(e)
          c = int(f)
          d = int(g)
          # print(b,c,d)

          d1 = abs(N-b)
          d2 = abs(N-c)
          d3 = abs(N-d)
          D = min(d1,d2,d3)
          res = []
          # if d1 == D:
          res.append(b)
          # if d2 == D:
          res.append(c)
          # if d3 == D:
          res.append(d)
          # print(res)
          return res

      l = []
      l.extend(getPalindrome(str(a)))
      # if f:
      l.extend(getPalindrome(str(b)))
      # print(l)
      l.append(555)
      l = set(l)
      # print(l)
      res = float('inf')
      for i in l:
        r = 0
        for j in nums:
          r += abs(j-i)
        # print(i,r)
        res = min(res,r)
      return res
        
341