<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 {
public:

    long long dig(string s) {
        long long ret = 0;
        for (int i = 0; i < s.length(); i++) {
            ret *= 10;
            ret += ((int) s[i] - '0');
        }
        return ret;
    }

    string tostring(long long n) {
        string ret = "";
        do {
            char c = (n%10) + '0';
            ret = c + ret;
            n /= 10;
        } while(n);
        return ret;
    }

    string pals(string s) {
        int slen = s.length();
        int l = (slen - 1) / 2;
        int r = slen / 2;
        while (l >= 0) {
            s[r] = s[l];
            l--;
            r++;
        }
        return s;
    }

    string nearestPalindromic(string n) {
        long long dign = dig(n);
        long long lf, rg;
        long long l = 0;
        long long r = dign - 1;
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long num = dig(pals(tostring(mid)));
            if (num < dign) {
                lf = num;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        l = dign + 1;
        r = 1e18;
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long num = dig(pals(tostring(mid)));
            if (num > dign) {
                rg = num;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        // cout << lf << ' ' << rg << ' ' << dign << endl;
        if (abs(lf - dign) <= abs(rg - dign)) return tostring(lf);
        return tostring(rg);
    }
};
11300