<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:
    bool ispal(string s){
        int i=0;
        while(s.size()/2>i){
            if(s[i]!=s[s.size()-1-i])return false;
            i++;
        }
        return true;
    }
    string nearestPalindromic(string n) {
        int sz=n.size();
        if(sz==1){
            if(n=="0")return "1";
            return to_string(stoi(n)-1);
        }
        string ans1=n;
        for(int i=sz/2;i<sz;i++){
            ans1[i]=ans1[sz-i-1];
        }
        string ans2="",ans3="";
        string firsthalf="";
        if(sz%2){
            for(int i=0;i<=sz/2;i++)firsthalf.push_back(n[i]);
            ans2=to_string(stol(firsthalf)+1);
            ans3=to_string(stol(firsthalf)-1);
            int i=sz/2-1;
            while(ans2.size()!=sz){
                ans2.push_back(ans2[i]);
                ans3.push_back(ans3[i]);
                i--;
            }
        }
        else{
            for(int i=0;i<sz/2;i++)firsthalf.push_back(n[i]);
            ans2=to_string(stol(firsthalf)+1);
            ans3=to_string(stol(firsthalf)-1);
            int i=sz/2-1;
            while(ans2.size()!=sz){
                ans2.push_back(ans2[i]);
                ans3.push_back(ans3[i]);
                i--;
            }
        }
        string ans4="",ans5="1";
        for(int i=0;i<sz-1;i++)ans4.push_back('9');
        while(ans5.size()<sz){
            ans5.push_back('0');
        }
        ans5.push_back('1');
        long long dist=3*1e18;
        string ans;
        vector<string> v;
        v.push_back(ans1);
        v.push_back(ans2);
        v.push_back(ans3);
        v.push_back(ans4);
        v.push_back(ans5);
        for(auto it:v){
            if(dist>abs(stol(n)-stol(it)) && stol(it)!=stol(n)){
                dist=abs(stol(n)-stol(it));
                ans=it;
                // cout<<dist<<" "<<it<<" "<<ans<<endl;
            }
            else if(dist==abs(stol(n)-stol(it)) && stol(it)!=stol(n)){
                if((stol(ans)>stol(it)))ans=it;
            }
        }
        return ans;
    }
};
9700