<p>Given a string <code>n</code> representing an integer, return <em>the closest integer (not including itself), which is a palindrome</em>. If there is a tie, return <em><strong>the smaller one</strong></em>.</p>

<p>The closest is defined as the absolute difference minimized between two integers.</p>

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

<pre>
<strong>Input:</strong> n = &quot;123&quot;
<strong>Output:</strong> &quot;121&quot;
</pre>

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

<pre>
<strong>Input:</strong> n = &quot;1&quot;
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong> 0 and 2 are the closest palindromes but we return the smallest which is 0.
</pre>

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

<ul>
	<li><code>1 &lt;= n.length &lt;= 18</code></li>
	<li><code>n</code> consists of only digits.</li>
	<li><code>n</code> does not have leading zeros.</li>
	<li><code>n</code> is representing an integer in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
</ul>

class Solution {
    long long getFirstHalf(string x) {
        int len = x.size();
        string half = x.substr(0, (len + 1) >> 1);
        return stol(half);
    }

    long long createNumber(long long firstHalf, bool even) {
        vector<int> d;
        auto copy = firstHalf;
        while (copy > 0) {
            d.push_back(copy % 10);
            copy /= 10;
        }

        if (!even) {
            d.erase(d.begin());
        }

        for (int i : d) {
            firstHalf = firstHalf * 10 + i;
        }

        return firstHalf;
    }

public:
    string nearestPalindromic(string n) {
        if (n == "1")
            return "0";
        int len = n.size();
        long long firstHalf = getFirstHalf(n);
        long long num = stoll(n);
        array<long long, 5> cand;
        cand[0] = createNumber(firstHalf, len % 2 == 0);
        cand[1] = createNumber(firstHalf + 1, len % 2 == 0);
        cand[2] = createNumber(firstHalf - 1, len % 2 == 0);
        cand[3] = static_cast<long long>(pow(10LL, len - 1)) - 1;
        cand[4] = static_cast<long long>(pow(10LL, len) + 1);
        long long best = LONG_LONG_MAX;
        long long answer = LONG_LONG_MAX;
        for (auto c : cand) {
            if (num == c)
                continue;
            long long now = abs(0LL + num - c);
            if (best > now) {
                best = now;
                answer = c;
            } else if (best == now) {
                answer = min(answer, c);
            }
        }
        return to_string(answer);
    }
};
8600