<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:
    typedef long long ll;
    string calc_next_pal(int i, string n){
        auto prev_n = n;
        int l = n.length();
        if (n[i] == '9') return "";
        n[i]++;
        for (int j = 0; j <= i; j++){
            n[l-1-j] = n[j];
        }
        for (int j = i + 1; j <= l-1-(i+1); j++){
            n[j] = '0';
        }
        if (prev_n == n) return "";
        return n;
    }
    string calc_prev_pal(int i, string n){
        auto prev_n = n;
        int l = n.length();
        if (n[i] == '0') return "";
        n[i]--;
        for (int j = 0; j <= i; j++){
            n[l-1-j] = n[j];
        }
        for (int j = i + 1; j <= l-1-(i+1); j++){
            n[j] = '9';
        }
        if (prev_n == n) return "";
        return n;
    }
    string palin(string s){
        string prev = s;
        int l = s.length();
        for (int j = 0; j < l; j++){
            s[l-1-j] = s[j];
        }
        if (prev == s) return "";
        else return s;
    }
    string nearestPalindromic(string n) {
        int l = n.length();
        set<ll> pal_set;
        string s = "";
        if (l == 1){
            s += (char)(n[0] - 1);
            return s;
        }
        pal_set.insert(stoll(string(l-1,(char)'9')));
        pal_set.insert(stoll("1" + string(l-1, (char)'0') + "1"));
        for(int i = 0; i < (l+1)/2; i++){
            string next = calc_next_pal(i,n);
            string prev = calc_prev_pal(i,n);
            if (next != "") pal_set.insert(stoll(next));
            if (prev != "") pal_set.insert(stoll(prev));
        }
        auto pal = palin(n);
        if (pal != "") pal_set.insert(stoll(pal));
        for (auto x : pal_set){
            cout << x << "\n";
        }
        auto it = pal_set.upper_bound(stoll(n));
        auto next = *it;
        it--;
        auto prev = *it;
        if (next - stoll(n) < stoll(n) - prev){
            return to_string(next);
        }
        else return to_string(prev);
    }
};
9800